Set Complement and Set Difference | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Set Complement and Set Difference

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

← The Universal Set and SubsetsNext lesson: Cardinality and Types of Subsets →

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

Combining 2 sets into a third - and shading the region each describes.

  • Compute unions and intersections
  • Compute complements, differences, and symmetric differences
  • Read each operation as a shaded Venn region
  • Prove De Morgan's laws for sets

Transcript

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

Set Theory and Functions

Set Operations: Complement and Difference

Chapter two has defined what a set is, and how one set sits inside a universal set. This section adds the operations that combine two sets into a third. We'll compute unions, intersections, complements, differences, and symmetric differences. We'll shade the region each one describes on a Venn diagram. And we'll prove De Morgan's laws for sets.

The Opening Problem

One Training Record, Many Lists

A company's learning-management system tracks which employees have completed each required security-training module. A compliance officer needs several lists from the same two tables of employee IDs. Everyone who still needs at least one module. Everyone who's fully compliant. Everyone who finished the phishing module, but not the password module. Each of those lists is, with no extra machinery, a set operation. And in a real database, each is a single query. Union, intersect, and except compute exactly the operations in this section, applied to two tables of IDs.

Definitions 2.3.1 and 2.3.2

Union and Intersection

The union of A and B is the set of all x such that x is in A, or x is in B. Everything in either set. The intersection of A and B is the set of all x such that x is in A, and x is in B. Everything in both. Here's the running example. The universal set is twelve employee IDs, one through twelve. A is the IDs who completed the phishing module, one through seven. B is those who completed the password module, four through ten. For the union, an ID belongs if it appears in at least one list. Every ID from one to ten does, while eleven and twelve appear in neither. That's everyone who completed at least one module. For the intersection, an ID belongs only if it's in both lists. Exactly four, five, six, and seven are. That's everyone who's fully compliant.

Definitions 2.3.3-2.3.5

Complement, Difference, Symmetric Difference

Three more operations round out the toolkit. The complement of A, written A prime, is the set of elements of the universal set that are not in A. It's U minus A, so it depends on U. The set difference, A minus B, is the set of elements in A but not in B. Equivalently, it's A intersect B prime, since not in B is exactly what B prime collects. And the symmetric difference of A and B is the set of elements in exactly one of them. It's A minus B, together with B minus A.

Worked Example, Continued

Who Still Needs What

Using the same sets, here are the results. A prime removes one through seven from one through twelve, leaving eight through twelve. Those employees still need the phishing module. A minus B keeps the IDs in A that aren't in B. That's one, two, and three. They completed phishing only, and still need the password module. B minus A, by the same check in the other direction, is eight, nine, and ten. They completed the password module only. And the symmetric difference is those two sets together. One, two, three, eight, nine, and ten. Everyone who completed exactly one module, and isn't yet fully compliant.

Figure 2.3.1 (1)

The Regions, Shaded

This figure shows the regions on a Venn diagram, with the universal set as the rectangle. The reference diagram shows how many IDs are in each region. Three in A only, four in both, three in B only, and two outside both. The union shades everything inside either circle. And the intersection shades only the overlap, where the two circles share their elements.

Figure 2.3.1 (2)

Complement, Difference, Symmetric Difference

Here are the other three operations, on the same layout. The complement of A shades everything in the rectangle outside circle A. That's why the complement depends on the universal set. A minus B shades the part of circle A that doesn't overlap B. And the symmetric difference shades both circles, except the overlap. It's the union, with the intersection removed.

Laws for Sets

Mirroring the Laws of Logic

These operations obey algebraic laws that mirror the logical laws from section one point six, term for term. Union behaves like or. Intersection behaves like and. And complement behaves like not. The distributive laws for sets say A intersect the quantity B union C equals A intersect B, union A intersect C. And the same holds with union and intersection swapped. De Morgan's laws for sets say the complement of A union B is A prime intersect B prime. And the complement of A intersect B is A prime union B prime.

Worked Proof

De Morgan's Law for Sets

Here's a general proof of the first De Morgan's law for sets, in the arbitrary-element style from section one point seven. Let x be an arbitrary element of the universal set. x is in the complement of A union B, if and only if x is not in A union B, by the definition of complement. By the definition of union, that holds if and only if it's not the case, that x is in A or x is in B. Next comes De Morgan's law for logic, cited from section one point six rather than re-derived. It says that holds if and only if x is not in A, and x is not in B. That's x in A prime and x in B prime. And that's exactly x in the intersection of A prime and B prime. Since x was arbitrary, the two sets are equal.

Checking a Distributive Law

One Case, Both Sides

A distributive law can also be checked for a specific case. Add a set C, the IDs who completed an optional data privacy workshop. Two, four, six, eight, ten, and twelve. On the left, B union C is two, four, five, six, seven, eight, nine, ten, and twelve. Intersect that with A, and you get two, four, five, six, and seven. On the right, A intersect B is four through seven, and A intersect C is two, four, and six. Their union is two, four, five, six, and seven. Both sides match, confirming the law for this case. The general proof is what covers every case.

Table 2.3.1

The Same Operations in SQL

This table pairs each operation with its direct SQL analogue, over two tables of IDs. Union is select from A, union, select from B. Intersection uses intersect. The complement selects the IDs from the universal table that are not in A. Difference uses except. And the symmetric difference is A except B, union, B except A. Set theory and query languages are describing the identical structure.

Takeaways

Every Operation Is a Region

To summarize. Union keeps elements in at least one set, and intersection keeps only elements in both. The complement depends on the universal set. The difference A minus B equals A intersect B prime. And the symmetric difference keeps elements in exactly one set. Every operation corresponds to a shaded region of a Venn diagram, and, for finite sets, to a concrete list you can check. And De Morgan's laws for sets mirror the logical laws from section one point six. Here's something to think about. Two sets split the universal set into four regions. Only A, only B, both, and neither. How many regions can three sets create? And must every region actually contain an element, or can some legitimately be empty?

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 Set Complement and Set Difference

What is the difference between set complement and set difference?
The complement A' contains every element of the universal set U that is not in A, while the difference A - B contains the elements of A that are not in B. The complement depends on U. The two are linked by A - B = A \cap B'.
How do you find A minus B, B minus A, and the symmetric difference of two sets?
Keep the elements of A that are not in B to get A - B, and do the reverse for B - A. The symmetric difference joins them: (A-B)\cup(B-A). For A=\{1,\dots,7\} and B=\{4,\dots,10\}, it is \{1,2,3,8,9,10\}, the elements in exactly one set.
How do you shade set complement, difference, and symmetric difference on a Venn diagram?
Shade A' as everything in the rectangle outside circle A. Shade A - B as the part of circle A that does not overlap B. Shade A \,\triangle\, B as both circles except the overlap, which is the union with the intersection removed. Because A' includes the area outside both circles, it depends on the universal set.
How do you prove De Morgan's law (A\cup B)' = A'\cap B' for sets?
Take an arbitrary element x and chain equivalences. x\in(A\cup B)' iff x\notin A\cup B, iff not (x\in A or x\in B). By De Morgan's law from logic, that is x\notin A and x\notin B, so x\in A'\cap B'. Since x was arbitrary, the two sets are equal.

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 →