Scire ad trascendere - Learn to transcend.

Topics covered:

  • Set-builder notation
  • Set operations: union, intersection, set difference, symmetric difference
  • Subset, power set
  • Using Boolean logic to prove set-related propositions
  • Logical quantifiers
  • Relation

Basic set theory

Conventions of notations

Special sets:

  • the set of natural numbers: 1
  • the set of integers:
  • the set of rational numbers:
  • the set of real numbers
  • the set of complex numbers
  • empty set:

Reserved symbols:

  • : universal set

Set-builder notation

Four ways to write set-builder notations:

Example: Toyota numbers

The following definitions of Toyota numbers are all equivalent:

Let be the set of positive integers.

Cardinality

The cardinality of set (denoted by ) is the number of objects in the set. We also call the size of the set .

Subset

Suppose and are sets. We say that is a subset of provided every element of is also an element of . The notation means is a subset of .

Important facts:

  1. A set is always a subset of itself.
  2. is the subset of any set.

Difference between and :

is an operator between two sets; is an operation between an element and a set.

Proving one set is a subset of another:

To show , you need to prove that every element of is also an element of . That is, for any given , if you can show also holds, then .

Equality of sets

If two sets have exactly the same elements, they are said to be equal.

Proving iff and :

() If , then both sets contains exactly the same elements. For any element , holds, which indicates . For any element , holds, which indicates .

() If both and are true, we know that every element of is also an element of ; every element of is also an element of . That is to say, and must contain exactly the same elements. Therefore, we have .

Proving two sets and are equal:

Method 1: Show and .

Method 2: Using set builder notation, show that two sets can be represented using the same set-builder notation.

Power set

Let be a set. The power set of (denoted by ) is the set of all subsets of .

Example: the power set of is the set

Number of elements in the power set:

Suppose , then . This is true because for each element in the set, there are two possibilities: it is either an element of the subset or not an element of the subset. Therefore, the total number of combinations is given by

The notation of power set is because .

Important conclusion (try to prove it yourself):

.

Set operations

  • Union: the union of and (denoted by ) is the set of elements that are in or (or both).
  • Intersection: the intersection of and (denoted by ) is the set of elements that are in both and .
  • Difference: the difference of and (denoted by ) is the set of all elements of that are not in .
  • Symmetric difference: the symmetric difference of and (denoted by ) is the set of elements in but not in or in but not in . More concretely, .
  • Cartesian product: the Cartesian product of and (denoted by ) is the set of all ordered pairs (two-element lists) formed by taking an element from A toghther with an element from in all possible ways.

Examples:

Suppose , , then:

Important facts (try to prove them yourself):

Each operation in terms of set-builder notation:

Remarks

  1. When you are asked to prove set equalities, you have two options: 1) proving mutual inclusion; 2) showing set-builder notations are equal. Personally, I prefer the latter because we only need to prove one direction to show the two sets are equal. Also, the use of pure mathematical language will help you understand and solve the problem faster.
  2. Think of as a Boolean variable. If is an element of , then is True; otherwise, it is False.
  3. is also a Boolean variable, which is logically equivalent to .
  4. Set difference is not the same as numerical difference. Some student write in their homework. This is basically assuming two facts:
    • Associativity: because you think
    • exists, and

    However, these properties cannot be used without proof! Therefore, do not assume these operations have any similarity to other numerical operations you know before. If you really need to use these properties, please prove them first.

Example: prove .

In your homework/exams, remember to point out the details of key steps (e.g. here, the use of distributive properties).

Example: prove iff .

Now you may see why you cannot treat set difference as numerical difference, because does not indicate !

The definition of is .

() If , then for every , must be also true. As a result, there is no element in that satisfies , which means is .

() If , it means that for all , must be false. Because is always true, it means that must be always false. That is to say, for all , must be always false, which means must be always true, which indicates .

Logical quantifiers

  • Existential quantifier: , assertions about

    Meaning: There exists in set , such that the assertion holds.

  • Universal quantifier: , assertion about

    Meaning: For all in , the assertion holds.

  • Combination of quantifiers:

    • , , assertion about and : there exists an element in , such that for all , the assertion holds.

    • , , assertion about and : for all in , there exists , such that the assertion holds.

Example: suppose is a function defined on . Use quantifiers to express “ has a maximum (denoted by )”.

, , .

Remarks.

Can you swap the order of the two quantifiers and say , , ?

No, you cannot. If you swap the order, it becomes for all , I can find a value , such that . Intuitively, I can just let , and the assertion always holds. In this case, has nothing to do with the maximum of .

Example: definition of limits (wiki)

means , , such that , if , then .

Suppose we know , think about this: we can assign an arbitrary number that is greater than zero, then their must exist a radius , such that when the “distance” between and () is less than , we have the “distance” between and () is less than . Think about when is very small, it indicates that the value of will be very close to , but also you need to make sure that is very close to . This definition concisely and accurately describes the behavior of limits.

Relations

  • A relation is a set of ordered pairs.

Example: On set , the relation can be represented by

  • means is related to by relation .

Note: means .

  • Let be a relation and let and be sets. We say is a relation on provided , and we say R is a relation from to provided .
  • Let be a relation. The inverse of , denoted by , is the relation formed by reserving the order of all ordered pairs in . In symbols, .

Example: On set , the inverse relation of is

which is clearly identical to the relation.

Important fact: (try to prove it yourself)

  • Properties of relations:
    • If , we have , we call reflexive.
    • If , we have , we call irreflexive.
    • If , we have , we call symmetric.
    • If , we have , we call antisymmetric.
    • If , we have , we call transitive.

Consider the relation on , where . It can be clearly seen that , will be False.

  1. It is not reflexive.
  2. It is irreflexive.
  3. It is symmetric, because is False, will be True due to vacuous truth.
  4. It is antisymmetric, because is False, will be True due to vacuous truth.
  5. It is transitive, because is False, will be False, and will be True due to vacuous truth.

Let , consider the relation on , where .

  1. It is not reflexive, because , .
  2. It is not irreflexive, because , .

Remarks.

We have shown that a relation can be symmetric and antisymmetric at the same time. We also show that a relation can be reflexive and irreflexive at the same time. Therefore, when dealing with relations, do not assume any properties. Use the definitions to form a rigorous proof.

Sample Q&A

Prove:

It is not difficult to see that:

To proceed with the proof, we want to show that iff and .

() If , every element of must be an element of and at the same time. Therefore, both and hold.

() If both and are true, then every element of must be in and at the same time. Therefore, , holds, which indicates .

This allows us to write .

Prove/disprove:

Using similar technique above, we have:

Right now, we need to consider: is equivalent to ? Definitely not! Suppose , and . Obviously but is not a subset of nor a subset of . Therefore, this statement is false.

A more formal disproof can be formulated in this way:

Let and . Then we have , which means . However, it is clear that and , so must not be a member of . Therefore, these two sets are not equal.

Which of the following statements are true and which are false?

  1. This is false. We can set , , then .

  2. This is false. No matter what value of we choose, we can always set so that that .

  3. This is true. No matter what value of is, we can always choose so that .

  4. This is true. We can choose , .

  5. (In following propositions, suppose )

  6. This is false. We can set , , then .

  7. This is true. We can choose , then it is less than or equal to all .

  8. This is true. No matter what value of is, we can always choose so that .

  9. This is true. We can choose , .

  1. Sometimes it is defined excluding 0