Discrete Math - 2.1.2 Set Relationships

Summary

This video explores the basics of set theory, including key concepts like set equality, subsets, proper subsets, cardinality, power sets, tuples, Cartesian products, and truth sets. It explains how sets are equal when they have the same elements, the distinction between subsets and proper subsets, and how to calculate the cardinality of a set. The video also touches on more advanced topics like power sets, ordered pairs in tuples, and Cartesian products, which form the foundation for understanding relationships and operations in set theory.

Takeaways

• 📘 Sets are equal if and only if they have the same elements, regardless of order or duplicates.
• ⚖️ A subset means every element of Set A is also an element of Set B.
• 🔄 A is a subset of B if A’s elements are in B, and proving this involves showing every element of A belongs to B.
• ❌ A is not a subset of B if there exists an element in A that is not in B.
• 🔁 A and B are equal sets if A is a subset of B and B is a subset of A.
• 🔄 A proper subset means A is a subset of B, but A and B are not equal because B has extra elements.
• 🔢 Cardinality refers to the number of distinct elements in a set.
• 🚫 The cardinality of the empty set is zero since it contains no elements.
• 💡 The power set is the set of all subsets of a set, and its cardinality is 2 to the power of the number of elements in the set.
• 🔗 A Cartesian product is the set of ordered pairs created by combining each element of Set A with each element of Set B.

Q & A

What does it mean for two sets to be equal?

Two sets are equal if they have exactly the same elements, regardless of the order or any duplicates. If every element of set A is in set B, and vice versa, the sets are equal.

What is a subset, and how is it denoted?

A subset is a set where all elements of set A are also elements of set B. It is denoted as A ⊆ B, meaning for all elements X, if X is in A, then X is also in B.

What distinguishes a subset from a proper subset?

A proper subset is a subset where all elements of A are in B, but A is not equal to B. In a proper subset, B contains at least one element that is not in A. It is denoted as A ⊂ B.

How do you prove that two sets are equal?

To prove two sets are equal, you need to show that A is a subset of B and B is a subset of A. If both conditions hold true, then A = B.

What is cardinality in relation to sets?

Cardinality refers to the number of distinct elements in a set. For example, the set {1, 2, 3, 3, 4} has a cardinality of 4 because there are four distinct elements: 1, 2, 3, and 4.

What is the power set of a set, and how is it calculated?

The power set is the set of all possible subsets of a set, including the empty set and the set itself. The number of subsets in the power set is 2 raised to the number of elements in the original set. For example, if set A has 3 elements, its power set will have 2^3 = 8 subsets.

What is a tuple, and how does it differ from a regular set?

A tuple is an ordered collection of elements, where the order matters. Unlike sets, where the order of elements is irrelevant, in tuples (e.g., (a1, a2)), the position of each element is significant.

What is the Cartesian product of two sets?

The Cartesian product of two sets A and B is the set of all possible ordered pairs (a, b), where a is an element of A, and b is an element of B. For example, if A = {0, 1} and B = {2, 3}, the Cartesian product would be {(0,2), (0,3), (1,2), (1,3)}.

What is a truth set?

A truth set is the set of all elements in a domain that make a given propositional function true. For example, if the propositional function is the absolute value of X = 3, then the truth set would be {-3, 3} because these values satisfy the equation.

How can you show that a set A is not a subset of set B?

To show that A is not a subset of B, you must find at least one element in A that is not in B. This single element proves that A ⊈ B.

Outlines

00:00

📚 Understanding Set Equality

This paragraph introduces the concept of set equality, explaining that sets are equal if they contain the same elements, regardless of order or duplication. The example demonstrates that the sets A = {0, 1, 1, 3, 4, 4} and B = {0, 1, 3, 4} are equal because they have the same unique elements. However, if set B includes an additional element (e.g., 5), the sets would no longer be equal. The notation used for set equality is also discussed.

05:02

🔗 Introduction to Subsets

The concept of subsets is introduced, where set A is a subset of set B if all elements of A are also elements of B. A Venn diagram is used to visualize this idea, and an example with sets A = {1, 2, 3} and B = {1, 2, 3, 4, 5} demonstrates how A is contained within B. The paragraph emphasizes the notation for subsets and explains how proving subset relationships is important in mathematical proofs. Additionally, it highlights that to prove A is not a subset of B, one must find an element in A that is not in B.

10:04

🔄 Subsets and Set Equality

This section explains how proving that set A is a subset of set B and that set B is a subset of set A allows one to conclude that A and B are equal. The paragraph introduces the difference between a subset and a proper subset. A proper subset means that set A is a subset of set B but not equal to it. For instance, if A = {1, 2, 3} and B = {1, 2, 3, 4}, then A is a proper subset of B since B contains an additional element. The proper subset notation and logic are also described.

🔢 Cardinality of Sets

The paragraph introduces the concept of cardinality, which refers to the number of distinct elements in a set. An example demonstrates how the cardinality of set A = {1, 2, 3, 3, 3, 4} is 4, as there are four distinct elements. The notation for cardinality uses absolute value brackets around the set. The paragraph also discusses the cardinality of other sets, such as the alphabet (26 letters) and the empty set (cardinality of 0).

🌀 The Power Set

This paragraph introduces the power set, which is the set of all subsets of a given set. For example, the power set of A = {0, 1, 2} includes subsets such as the empty set, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, and {0, 1, 2}. The cardinality of a power set is 2^n, where n is the number of elements in the original set. For the given example, A has three elements, so the power set has 8 subsets.

🧮 Cartesian Product and Ordered Pairs

This section introduces tuples, which are ordered collections of elements, and explains how ordered pairs (such as (a, b)) differ from unordered sets. The Cartesian product of two sets A and B is defined as the set of all ordered pairs (a, b) where a is an element of A and b is an element of B. An example demonstrates how the Cartesian product is calculated for sets A = {0, 1} and B = {2, 3, 4}, resulting in ordered pairs such as (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), and (1, 4).

✔️ Truth Sets and Propositional Logic

The paragraph introduces the concept of a truth set, which consists of elements from a domain that satisfy a given propositional function. For example, if the propositional function states that the absolute value of x is equal to 3, the truth set would be {−3, 3}, as these are the values that make the statement true. The notation for truth sets and their role in propositional logic is briefly discussed.

Keywords

💡Set Equality

Set equality refers to when two sets contain exactly the same elements. This means every element in one set must also be in the other, regardless of the order or duplicates. For example, in the video, set A = {0, 1, 1, 3, 4} is equal to set B = {0, 1, 3, 4}, because they contain the same elements.

💡Subset

A subset is a set whose elements are all contained within another set. For instance, if set A = {1, 2, 3} and set B = {1, 2, 3, 4, 5}, then A is a subset of B because all elements of A are in B. The video explains this using a Venn diagram to show the relationship between subsets.

💡Proper Subset

A proper subset is a subset that is not equal to the set it is contained within. This means that a proper subset has fewer elements than the set it is a part of. In the video, set A = {1, 2, 3} is a proper subset of set B = {1, 2, 3, 4}, as B contains elements not in A (such as 4).

💡Cardinality

Cardinality refers to the number of distinct elements in a set. For example, if set A = {1, 2, 3, 3, 4}, the cardinality of A is 4 because there are four distinct elements: 1, 2, 3, and 4. The video emphasizes that duplicates are not counted in determining cardinality.

💡Power Set

A power set is the set of all possible subsets of a given set, including the empty set and the set itself. For example, if set A = {0, 1, 2}, the power set of A includes the empty set, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, and {0, 1, 2}. The video explains how the number of elements in a power set can be calculated as 2^n, where n is the number of elements in the original set.

💡Ordered Pair

An ordered pair is a collection of two elements where the order of the elements matters. In the video, an example is given of ordered pairs like (5, 2) and (2, 5), which are considered different because the order of the numbers affects their identity. Ordered pairs are used in Cartesian products to describe relationships between two sets.

💡Cartesian Product

The Cartesian product of two sets is the set of all possible ordered pairs that can be formed by combining elements from the two sets. For example, if set A = {0, 1} and set B = {2, 3, 4}, the Cartesian product of A and B would be {(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4)}. The video introduces this concept to explain how relationships between sets can be defined.

💡Truth Set

A truth set is the set of all elements in a domain that satisfy a given condition or make a propositional function true. In the video, the example is given of the propositional function 'the absolute value of x equals 3.' The truth set for this would be {3, -3}, as these values make the statement true.

💡Predicate Logic

Predicate logic is a formal system used to express statements that can be true or false depending on the values of variables. In the context of the video, it is used to describe conditions like 'for all x, if x belongs to A, then x belongs to B,' which helps in proving relationships like subsets and set equality.

💡Distinct Elements

Distinct elements are the unique elements in a set, with duplicates being counted only once. The video uses this concept to explain cardinality, such as when set A = {1, 2, 3, 3, 4} is said to have four distinct elements (1, 2, 3, and 4), even though the number 3 appears multiple times.

Highlights

Sets are equal if and only if they have the same elements, regardless of order or duplicates.

A subset is when all elements of set A are also elements of set B, as represented in Venn diagrams.

If set A is a subset of set B, and set B is a subset of set A, then the sets are equal.

A proper subset is when all elements of set A are in set B, but the two sets are not equal, meaning B has additional elements.

Cardinality represents the number of distinct elements in a set, with repeated elements not affecting the count.

The power set is the set of all subsets of a given set, with its cardinality calculated as 2^n, where n is the number of elements in the original set.

Tuples are ordered collections of elements, which differ from sets because the order of elements matters in tuples.

Cartesian products are sets of ordered pairs formed by combining every element of set A with every element of set B.

Relations can be viewed as subsets of Cartesian products, where specific ordered pairs meet a certain condition.

The truth set of a propositional function consists of all elements that make the statement true for a given domain.

To prove that set A is a subset of set B, you must show that every element in A is also in B.

Finding that a single element in set A is not in set B disproves that A is a subset of B.

Ordered pairs are fundamental in understanding Cartesian products, where the sequence of elements matters.

Cardinality of the empty set is always zero because it contains no elements.

In Cartesian products, each element from one set is paired with every element from another set to form ordered pairs.

Transcripts

in this video we're going to explore set

relationships so again there's going to

be just a lot of terminology here a lot

of definitions but do your best to kind

of understand the basics so that as we

move through the rest of this unit

talking about sets that you don't get

lost in the notation so here we're

talking about set equality and sets are

equal if and only if they have the same

elements so first notice the way that

this is notated I'm saying for all X X

is a cell X is an element of a if and

only if X is an element of B and we

would just write that a equals B so

let's say I have set a is 0 1 1 3 4 4

and set B is 0 1 3 for these our equal

sets so I can say here that set a is

equal to set B because even though I

have a duplicate of 1 in a duplicate of

4 there are no elements that are in one

set that are not in the other set and

again it doesn't matter the order it

doesn't matter if there are duplicates

however if B included 5 now all of the

sudden a is not equal to B so those sets

would no longer be equal because B has a

value or an element of 5 that is not

contained in set a now let's talk about

a subset a subset or as set a is a

subset of B if and only if every element

of a is also an element of B so let's

take a look at a Venn diagram before we

look at the notation that we might use

if I have a Venn diagram a subset might

look like this so we've got some

universe out here

and this would be set a and this would

be set B so essentially what I'm saying

is anything in set a is also contained

in set B so let's say a is the set of

elements 1 2 3 and B is the set of

elements 1 2 3 4 5 so if I were putting

these values on on my then 1 2 & 3 would

all be in set a 4 & 5 would be in set B

but notice that everything in set a is

also contained in set B so this would be

a subset again this is the notation that

we would use we're saying for all X's if

X is an element in a then X's and

elements in B and then this is the

notation that we will use so I want you

to kind of think about this as like a

less than or equal to B essentially

saying everything in a is in B and maybe

they're exactly the same

that maybe they're not so a little bit

more on subsets if I'm going to show

that a is a subset of B essentially I

have to show that every element

of a belongs to be

oops belongs to B that was a horrible B

every element of a belongs to B so I'm

saying if X belongs to a then X belongs

to B now why is it important to know

this because obviously there will be

some proof involved and this is the way

that we will go about that proof is to

show that if it belongs to a then it

belongs to B as well obviously if I want

to show that a is not a subset of B all

I have to do is find some example that

shows that it's not true essentially so

I'm going to find an element if there

exists some element X that belongs to a

that does not belong to B essentially is

what I want to do so show it belongs to

a belongs to set a but not set the

and the last one says show a is a subset

of B and B is a subset of a now why

would this be important because if this

is true thinking about it this way a is

less than or equal to B B is less than

or equal to a if both of those are true

what could we say it we could state that

a is equal to B so that's essentially

what we're going to do and this one's

super important because this is how you

will prove that a is equal to B is to

show that both of those statements are

true so you're proving that the subset

of a or that a is a subset of B that B

is a subset of a and therefore a and B

are equal sets so now that we understand

a subset it's important to understand

the difference between the subset and a

proper subset so with our subsets we

said a was a subset of B and we used

this line to denote that they could in

fact be the exact same set so here we're

talking about a proper subset and note

how my notation is just going to change

a little bit a proper subset says that a

is a subset of B but that they are not

equal to one another therefore we have

some elements in B that's not contained

in a so let's say a was that set of one

two three if B was the set of one two

three I could say a is a subset of B and

B is a subset of a and therefore a and B

are equal sets however if B

is now 1 2 3 4 a is still a subset of B

but B is not a subset of a these are not

equal and therefore a is a proper subset

of B and it's proper because we've got

this one little guy in set V that is not

contained in a and again here is the

longer version using our predicate logic

for all X's if X belongs to a then X

belongs to B and there exists some

element that belongs to B and that does

not belong to a so that is a proper

subset so now we want to talk about

cardinality and cardinality is just

essentially the size of your set so

cardinality is the number of distinct

elements of a set and of course distinct

being important here let's say set a is

1 2 3 3 3 4 then the cardinality of a

and notice that notation is just using

essentially like the absolute value

bracket on each side this is saying how

many distinct elements are there there's

1 2 3 4 distinct elements so 3 3 3

there's three of them so those aren't

all distinct but you get the idea so the

notation again is just that's what tells

me that I'm finding the cardinality or

the number of elements in the set so

let's say I wanted to find the number of

elements in the set of the alphabet oops

maybe try to spell alphabet correctly

well there are 26 letters of the

alphabet and so that would be the

cardinality of that set

the cardinality of the empty set

hopefully we all know that zero because

the empty set is saying that there is

nothing in the set now I want to

introduce you to a couple of concepts

that really this is just an introduction

but as we move forward through this

course we will use these concepts again

and again so the first of those is the

power set and the power set is the set

of all subsets of a set so for instance

let's say set a is 0 1 2 if I want the

power set of a then I want all of the

subsets so the subset would be the empty

set because again I'm looking at these

elements I could have none of those

elements I could have one of those

elements so 0 1 2 I could have two of

those elements 0 1 0 2

or one two or I could have three of

those elements zero one two now keep in

mind because order doesn't matter I

wouldn't have to write 0 1 and 1 0

because those are the same set so how

many elements does the power set have

one two three four five six seven eight

so the cardinality of the power set of a

is 8 and again we'll talk more in depth

about this later but if you ever want

the cardinality of the power set of a

set of a set whoa

getting crazy of a set with n elements

is 2 to the N so here I had three

elements and therefore two to the third

was 8 and that is exactly how many we

found so this brings us to tuples and a

temple is important because basically

it's an ordered collection that has a

sub 1 as its first element a sub 2 is

its second element etc etc obviously the

way that we would have seen this most

often is in ordered pairs so a comma set

a 1 comma a 2 you get the idea it's

basically just two values but the

important thing here is that it's

ordered whereas when we're just looking

at a normal set we don't worry about the

order but ordered pairs obviously the

ordered pair of 5 2 is not the same as

the ordered pair of 2 5 those are very

different points on our Cartesian plane

so I bring up ordered temples because of

the Cartesian product which we will talk

much more about when we talk about

relations further along in this course

but it's essentially the set of ordered

pairs a comma B where a each element a

belongs to the set a and each element B

belongs to the set B resulting from a

times B so let's say set a is 0 and 1

and set B is 2 3 4 what a Cartesian

product tells us to do is it's going to

be all of the ordered pairs that I can

create using one element of a and one

element of B so I could have 0 comma 2 I

could have 0 comma 3 0 comma 4 or I

could have 1 comma 2 1 comma 3 1 comma 4

so again each time I used a value from

set a when an element from set B and

I've done all of the different

combinations

again I said later on we'll talk about

relations but let's say I had a subset

are that included just 0 2 & 1 2 this

would be considered a relation because

it is a subset of that Cartesian product

lastly let's take a look at what is

called H root set a true set of P is the

set of elements X in the domain such

that P of X is true so obviously this is

some sort of propositional function and

we're saying the truth set is any values

that make P of X true

so our notation says X is an element of

D D is obviously the domain such that P

of X is true so let's say the domain

here is the integers and let's say P of

X represents the statement that the

absolute value of X is equal to 3 well

if that's the case then the truth set

would be the set of all values that I

could put in here to make it true so

what values of X would make the absolute

value of x equals 3 true and of course

that would be negative 3 and positive 3

so that would be the truth set because

I'm looking for any values that I can

plug in for X and get a true value so

the absolute value of negative 3 is 3

and the absolute value of positive 3 is

3

coming up next we're going to take a

look at operations on sets