The Universal Set and Subsets | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

The Universal Set and Subsets

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.2 · lesson 10 of 878 min · free with a free account

← Sets and Set NotationNext lesson: Set Complement and Set Difference →

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

Every role is a subset of the permission catalog.

  • Define the universal set for a given context
  • Distinguish a subset from a proper subset
  • Build a power set, and count its elements
  • Read subset relationships from a Venn diagram

Transcript

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

Set Theory and Functions

The Universal Set and Subsets

This section introduces the universal set, subsets, and the power set. We'll distinguish a subset from a proper subset, count exactly how many subsets a finite set has, and read subset relationships from a Venn diagram. And the running example comes straight from cloud security.

The Opening Problem

A Catalog of Every Permission

A cloud identity-and-access-management system, or IAM system, defines a fixed catalog of every action a user could ever be granted. Read a file, delete a database, invite a teammate, view a billing statement, and so on. Nothing outside that catalog exists, as far as the system is concerned. No role can be given a permission the platform hasn't already defined. That fixed catalog is exactly what mathematicians call a universal set. When a security team designs a new role, such as read-only analyst, they're literally selecting a subset of that catalog. And whether one role sits entirely inside another, or how many roles a catalog could possibly produce, is exactly the mathematics of subsets and power sets.

Definition 2.2.1

The Universal Set

The universal set, written U, is the set of every object under consideration in a given context. Every other set in that context is understood to be a subset of U, and nothing outside U is ever considered. For the IAM system, fix U as the whole permission catalog. Read, write, and delete file. Invite and remove user. View and edit billing. And deploy and delete service. That's nine permissions. Every role the platform can ever define is built entirely from these nine. U isn't an absolute collection of everything that exists. For course registration, it might be every enrolled student. For a database, every row in a table. It changes with the problem. But within a single problem, it stays fixed.

Definitions 2.2.2 and 2.2.3

Subset and Proper Subset

A is a subset of B if every element of A is also an element of B. Formally, for every x, if x is in A, then x is in B. A is a proper subset of B if A is a subset of B, and A isn't equal to B. So B contains at least one element that A doesn't. Two consequences are worth stating. First, every set is a subset of itself. If x is in A, then x is in A, whatever x is chosen. But a set is never a proper subset of itself, since that would require A not equal to A. Second, the empty set is a subset of every set, including itself. The condition, if x is in the empty set then x is in A, has a hypothesis that no x ever satisfies. So it's vacuously true, whatever A is.

Checking Roles

Which Role Sits Inside Which?

Now define three roles from the catalog. Read-only analyst has read file and view billing. Billing manager has those two, plus edit billing. Check element by element. Read file and view billing are both in billing manager. So read-only analyst is a subset of billing manager. And billing manager also has edit billing, which read-only analyst doesn't. So the two aren't equal, and read-only analyst is a proper subset. Now a third role, deployment engineer, with deploy service and delete service. Neither belongs to billing manager. And read file, for instance, isn't in deployment engineer. So neither role is a subset of the other. But both are still proper subsets of the universal set, which contains every permission either could draw from.

Chaining

Subset Relationships Chain

Subset relationships also chain together. If A is a subset of B, and B is a subset of C, then A is a subset of C. Here's why. Take any element x of A. Since A is a subset of B, x is in B. And since B is a subset of C, x is in C. Because x was an arbitrary element of A, every element of A is in C. That's exactly the condition for A to be a subset of C. Applied to the roles, read-only analyst is inside billing manager, and billing manager is inside U. So read-only analyst is inside U, without checking it against all nine permissions directly.

Definition 2.2.4

The Power Set

The power set of a set A is the set of all subsets of A, including the empty set and A itself. Take A to be the read-only analyst role, read file and view billing. A set with two elements. Every subset is built by deciding, independently for each element, whether to include it or leave it out. Include neither, and you get the empty set. Include only read file, or only view billing, and you get the two singletons. Include both, and you get A itself. Four subsets in all. And the last one, A itself, is the only subset that isn't a proper subset.

Counting Subsets

Counting Every Subset

In general, if a finite set has n elements, each one can independently be included or excluded. That's two choices per element, made n times. Two times two, n times over, which is two to the n subsets. For the two-element role, that's two squared, which is four, exactly as listed. Cardinality beyond finite sets comes in section two point four. Apply the same count to the full catalog, with its nine permissions. Its power set has two to the ninth, which is five hundred twelve subsets. That's five hundred twelve conceivable roles, from one with no permissions to one with every permission. It's precisely why real platforms don't offer a menu of every possible subset. Administrators compose a role from named permissions, and the platform builds exactly the subset needed.

Venn Diagrams

Drawing Subset Relationships

A Venn diagram draws the universal set as a bounding rectangle, and every other set as a circle inside it. A subset relationship is drawn by nesting circle A entirely inside circle B. For a proper subset, the nesting is the same, but some region of B must lie outside A. It represents the elements B has that A doesn't. When neither set is a subset of the other, no valid nesting exists. The clearest drawing is two circles that don't overlap at all, when the sets share no elements.

Figure 2.2.1

The Roles as Venn Diagrams

This figure shows the roles as Venn diagrams. Panel A nests read-only analyst inside billing manager, inside U. That matches the proper-subset chain we verified. The ring between the two inner circles is edit billing, the one permission billing manager has that read-only analyst doesn't. Panel B draws billing manager and deployment engineer as two circles that don't touch. That correctly shows the two roles share no permissions, and that neither is a subset of the other.

Table 2.2.3

Subset vs Proper Subset

This table puts the two relationships side by side. A subset is defined by, for every x, if x is in A then x is in B. Equality is allowed. A proper subset also requires A not equal to B. Equality is excluded. So the two relationships differ only in whether A and B are allowed to be equal.

Takeaways

Subsets of a Fixed Universe

To summarize. The universal set fixes the domain of discourse for a context, and it changes from problem to problem. A subset of B may equal B. A proper subset requires B to contain at least one element A doesn't. The empty set is a subset of every set, including itself, because the defining conditional is vacuously true. A finite set with n elements has exactly two to the n subsets. And Venn diagrams show subsets by nesting one circle inside another. Here's something to think about. A student argues that the empty set has nothing to contribute, so it can't be a subset of anything. Using the formal definition, explain precisely what's wrong. And what does it reveal about a conditional being true, versus its hypothesis ever being satisfied?

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 The Universal Set and Subsets

What is the difference between a subset and a proper subset?
A subset allows equality, while a proper subset does not. A \subseteq B means every element of A is in B, so A may equal B. A \subset B (proper) also requires A \neq B, so B has at least one element not in A. Every set is a subset of itself, but never a proper subset of itself.
How many subsets does a set with n elements have, and what is a power set?
A set with n elements has 2^n subsets. The power set of A is the set of all subsets of A, including \varnothing and A itself. Each element is either included or excluded, giving two choices per element. For A=\{1,2\}, the power set is \{\varnothing,\{1\},\{2\},\{1,2\}\}, which has 2^2=4 elements.
Why is the empty set a subset of every set?
The empty set is a subset of every set because the defining condition is vacuously true. The statement "if x\in\varnothing, then x\in A" has a hypothesis that no x satisfies, so it cannot fail. A conditional with a false hypothesis is true. Therefore \varnothing\subseteq A for any set A, including A=\varnothing.
How do you show a subset relationship in a Venn diagram?
Draw the universal set U as a rectangle and nest circle A entirely inside circle B to show A\subseteq B. For a proper subset, some region of B must lie outside A, representing elements of B not in A. If neither set is a subset of the other, no nesting is valid. Two non-overlapping circles are the clearest drawing when the sets share no elements.

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 →