Cardinality and Types of Subsets | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 2.4 Free with a free account

Cardinality and Types of Subsets

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.4 · lesson 12 of 879 min · free with a free account

← Set Complement and Set DifferenceNext lesson: Partially Ordered Sets and Lattices →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

How many elements - and how many ways to choose among them.

  • Find the cardinality of a finite set
  • Prove the formula for the number of subsets
  • Distinguish finite from infinite sets
  • Count the subsets of a given size by systematic listing

Transcript

Everything said in the video, section by section (1,261 words). Read along, or search it.

Set Theory and Functions

Cardinality and Types of Subsets

This section is about cardinality, a precise count of how many elements a set contains. We'll use it to count exactly how many subsets a set has, and prove the formula. We'll separate finite sets from infinite ones. And we'll count the subsets of a particular size, by careful, systematic listing.

The Opening Problem

How Many Ways to Share One Document?

A small product team keeps its internal documents in a shared workspace. Every document has an owner, who decides exactly which teammates can see it. Not a role, not a department, but a specific group of individual people. With three teammates, Amara, Ben, and Chloe, the owner might share with just Amara, with Amara and Chloe, with everyone, or with no one else at all. Before the access-control code can be trusted, the engineers need an answer. Exactly how many sharing configurations are possible for one document, for a team of a given size? For three people, it's easy to list them all. For the fifty-person company the product grows into, listing becomes hopeless. Yet the question still has an exact answer. The tool for answering it is cardinality.

Definition 2.4.1

The Cardinality of a Finite Set

For a finite set A, the cardinality of A, written with vertical bars around A, is the number of distinct elements A contains. Because a set can't contain the same element twice, cardinality is always a plain count, with no risk of double-counting. The empty set has cardinality zero. And the team, Amara, Ben, and Chloe, has cardinality three. Cardinality doesn't care about order, or how many times an element was mentioned. Chloe, Amara, Ben is the same set, with the same cardinality, three.

Theorem 2.4.1

The Size of the Power Set

Recall that the power set of A is the set of all subsets of A, including the empty set and A itself. The sharing question is exactly this. What is the cardinality of the power set of A? Here's the theorem. If A has n elements, its power set has two to the n elements. The proof. A subset is completely determined by one yes-or-no decision per element of A. Each element is either in the subset, or it isn't. The decisions are independent. Including one element places no restriction on any other. And every combination of decisions gives a distinct, valid subset. By the multiplication principle, which chapter five develops, n independent two-way decisions can be made in two times two, n times over, which is two to the n ways. That counts every subset exactly once. So the power set has two to the n elements.

Table 2.4.1

All 8 Sharing Configurations

For the three-person team, n is three, so the power set has two cubed, which is eight elements. This table lists all eight, confirming the count directly. The empty set. Each of the three singletons. The three pairs. And the whole team. Notice that the empty set and the full set both appear. Each is a completely ordinary member of the power set, not a special case to set aside.

Exponential Growth

50 People, a Quadrillion Configurations

The growth from n to two to the n is not gentle. A fifty-person workspace has two to the fiftieth possible sharing configurations for a single document. That's about one point one quadrillion. And fifty people is a perfectly ordinary company size. That's precisely why real access-control systems don't work directly with arbitrary subsets of users. Enumerating or auditing a quadrillion possibilities isn't feasible. Instead, production systems grant access through structured roles and groups. That cuts the space of configurations an administrator actually has to reason about down to a manageable size.

Definition 2.4.2

Finite and Infinite Sets

A set A is finite if its cardinality is n for some natural number n, including zero, for the empty set. A set that isn't finite is infinite. Everything so far assumed A was finite, and that assumption was doing real work. Counting the elements only gives a natural number when the counting eventually stops. The positive integers used for page numbers can be counted one at a time, but the counting never finishes. So the set is infinite. And infinite sets aren't all the same size. Some, called countably infinite, can be listed in a never-ending sequence that eventually reaches any given element. The integers are like this, and so is the set of all usernames of unbounded length. Others, called uncountable, are provably too large to list in any sequence. The real numbers are the standard example. Proving that takes real work, and comes later. So the formula two to the n presupposes a finite n. It doesn't extend to infinite sets by substituting a symbol for infinity.

Table 2.4.2

Grouping Subsets by Size

The table of subsets holds more information than the total of eight. Every subset has a definite size, from zero to three. Size zero appears once, the empty set. Size one appears three times, the three singletons. Size two appears three times, the three pairs. And size three appears once, the whole team. Every subset falls into exactly one size group. So the counts must add up to the total. One plus three plus three plus one is eight, which is two cubed.

Figure 2.4.1

The Power Set, Arranged by Size

This figure arranges every subset of a, b, c by size. The empty set is at the bottom, and the whole set, a, b, c, is at the top. A line joins two subsets whenever one is formed from the other by adding a single element. Each row is one of the size classes. Reading from bottom to top retraces the same size-zero-through-three structure as the table. Ordered by inclusion like this, it's called a Hasse diagram. We'll meet those again in the next section.

2 Patterns

Sums and Symmetry

Two patterns are worth noticing, from this one example. First, the size-group counts always add up to the size of the power set. Grouping by size sorts every subset into exactly one group, with nothing left over, and nothing counted twice. Second, the counts are symmetric. Size zero and size three both have a count of one. Size one and size two both have a count of three. That isn't a coincidence special to this example. Choosing which two of three teammates to include, is the same act as choosing which single teammate to leave out. So those two counts must match.

Counting a Given Size

Listing Systematically

The counts grow quickly, even for small sets. Add a fourth teammate, Deshawn. Now the power set has two to the fourth, which is sixteen subsets. To list the pairs, always name the alphabetically earlier teammate first, so no pair is listed twice. Amara with Ben, Chloe, and Deshawn. Then Ben with Chloe and Deshawn. Then Chloe with Deshawn. Six pairs. Direct listing still works at four, but the bookkeeping is already more delicate. By fifty, listing pairs by hand isn't realistic, though the question is just as well-posed. A general formula for the number of subsets of a given size, for any n and k, is one of the central results of chapter five.

Takeaways

Counting Elements, Counting Subsets

To summarize. The cardinality of a finite set is the count of its distinct elements. The empty set has cardinality zero. A finite set with n elements has exactly two to the n subsets, because each element is independently in or out. For infinite sets, counting elements one at a time, and the formula, no longer apply in the same way. And the subsets of an n-element set sort into size classes that partition the power set. Their counts sum to two to the n, and are symmetric. Here's something to think about. The set of all email addresses, with no length limit, is infinite. Does the power-set formula still make sense for it? If not, what exactly breaks down? The power set itself, the meaning of cardinality, or just the formula?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Cardinality and Types of Subsets

How many subsets does a set with n elements have?
A set with n elements has 2^n subsets, counting the empty set and the set itself. Each element is either in a subset or out, and these n yes-or-no choices are independent. By the multiplication principle, that gives 2\cdot 2\cdots 2 = 2^n distinct subsets. For example, \{a,b,c\} has 2^3 = 8 subsets.
What is the cardinality of a set, and how do you find it?
The cardinality of a finite set A, written |A|, is the number of distinct elements in it. Count each element once; order and repeats do not matter. So |\{a,b,c\}| = 3, and writing the same set as \{c,a,b\} changes nothing. The empty set has |\varnothing| = 0.
What is the difference between a finite and an infinite set?
A set is finite if its cardinality is some natural number n, including 0 for the empty set; otherwise it is infinite. Counting a finite set eventually stops, while counting the positive integers never does. Infinite sets also differ in size: the integers are countably infinite, but the real numbers are uncountable. The formula 2^n assumes a finite n.
How do you list all subsets of a given size without missing any or repeating?
List subsets of a given size systematically by sorting the elements and always naming the earlier element first, so no subset appears twice. For \{A,B,C,D\}, the pairs are AB, AC, AD, then BC, BD, then CD, giving 6. Sorting subsets by size also gives a check: the counts must add up to 2^n, here 1+4+6+4+1=16.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →