The basic concept of sets

Element of a set

Belong to ∈ \ ∈ in

Empty set ∅\varnothing∅ full set

Finite set, infinite set

Collection of yuan prime (base) : special: | ∅ \ varnothing ∅ | = 0, | {∅ \ varnothing ∅} | = 1

The characteristics of set: determinism, mutuality, disorder and diversity

Set equality: Two sets A and B have exactly the same elements

Subset: Let A and B be two sets. If elements of A are all elements of B, A is A subset of B, B contains A, or A contained in B is described as A ⊆\subseteq⊆B

For A ⊆ subseteq⊆B, and A ≠ ne=B, A is said to be A proper subset of B, and also B really contains A, or A really contains B, as A ⊂\subset⊂B

Operations and properties of sets:

And sets (the Union) :

Intersection (Intersection computes) :

Difference set (Difference) :

I set (Complement) :

Ring sum (symmetry difference) :

Ring product:

The arithmetic law of sets:

Proof of set:

Power and Cartesian product of a set:

Properties of power sets:

Ordered n-tuple :(a1,a2… ,an)

Ordered pairs: When n=2, they are called ordered pairs, also called ordered pairs, or ordered binary pairs

Ordered pair characteristics:

  1. If a ≠\ne=b, then (a, b) ≠\ne= (b, a)
  2. Two ordered pairs (a,b) and (c,d) are equal if and only if a=c,b =d

Cartesian Product:

Properties of the Cartesian product:

  1. A * \ times * B | | = | | | x \ times x | B;

  2. For any set A, there is A ×\times× ∅\varnothing∅= ∅\varnothing∅, ∅\varnothing∅ ×\times×A= ∅\varnothing∅;

  3. The cartesian product operation does not satisfy the commutative law, i.e. A ×\times×B ≠\ne=B ×\times×A;

  4. The cartesian product operation does not satisfy the associative law, i.e. (A ×\times×B) ×\times×C ≠\ne=A ×\times×(B ×\times×C)

  5. The Cartesian product satisfies the distributive law of union and intersection

  6. Let A, B, C, and D be sets. If A ⊆ subseteq⊆C and B subset subseteq⊆D, then A × times×B subset subseteq⊆C × times×D.

Common methods to prove the inclusion relation of sets:

  1. Using the definition: first take any x ∈\in∈A, and then deductively prove that x ∈\in∈B is true
  2. Try to find A set T that satisfies A ⊆\subseteq⊆T and T ⊆\subseteq⊆B, from the transitivity of inclusion relations having A ⊆\subseteq⊆B.
  3. Use the equivalent definition of A ⊆\subseteq⊆B, that is,A ∪\cup∪B=B,A ∩\cap∩B=A or a-b = ∅\varnothing∅.
  4. New inclusions are obtained by using union and intersection operations of known inclusions
  5. Reduction to absurdity

Common ways to prove the equality of sets:

  1. If A and B are finite sets, A=B can be proved by comparing all elements in the two sets one by one. If A and B are infinite sets, A ⊆\subseteq⊆ B, B subset teq⊆ A can be proved by proving the set inclusion relationship

  2. Reduction to absurdity

  3. By using the basic arithmetic law of set and the proved set equality, the set of left (right) edge of the equation to be proved is converted to the set of right (left) edge through equality transformation, or the transformation of both sides to the same set

Relationship between

The empty relation in a non-empty set is antireflexive, symmetric, antisymmetric and transitive, but not reflexive;

Empty relations in empty sets are reflexive, antireflexive, symmetric, antisymmetric and transitive.

Definition of a relationship: xRy

Relationship characteristics:

  1. Any subset of A ×\times×A is A relation on A

  2. If | A | = n, then A relationship of two n22 ^ {\ mathrm 2} {n} ^ 2 n2

  3. There are three special relations on A, i.e

    Empty relational ∅\varnothing∅;

    Global relation EA=A ×\times×A;

    Equal relationship IA = {(x, x) ∈ \ | x ∈ a.} in

Expression of relation:

  1. The set represents:

    Set A = {1, 2, 3, 4}, A relationship on R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2)}

  2. Relationship matrix

  3. Diagram:

Operation of a relation as a set:

  1. Relationship of: R studying S = {(x, y) ∈ \ | x ∈ a. in y ∈ \ in ∈ a. xRy and xSy}
  2. Relationship and: R ∪ S = {(x, y) ∈ \ | x ∈ a. in y ∈ \ in ∈ a. xRy or xSy}
  3. Relationship of the poor: R – S = {(x, y) ∈ \ | x ∈ a. in y ∈ \ in ∈ a. xRy and xS/y}

Inverse relationship: R – 1 = {(y, x) ∈ \ | x ∈ a. in y ∈ \ in ∈ a., and has the xRy}

Product of Relations: Call the relation R•S the product or composition of the relation R and S

Conclusion of the multiplication of relations:

  1. The multiplication of relations does not satisfy the commutative law
  2. The multiplication of relations satisfies the associative law

Relations of power

1.2.1 theorem:


  1. R m ⋅ R n = R m + n \mathrm{R}^{\mathrm{m}}\cdot \mathrm{R}^{\mathrm{n}}=\mathrm{R}^{\mathrm{m}+\mathrm{n}}

  2. ( R m ) n = R m n \left( \mathrm{R}^{\mathrm{m}} \right) ^{\mathrm{n}}=\mathrm{R}^{\mathrm{mn}}

1.2.3 theorem:

Several special relations and characteristics:

  1. Reflexive relation:

  2. Anti reflexive relation

  1. Symmetric relation

  2. Antisymmetric relation

  3. Transitive relation

    Theorem 1.2.4: it is A R2⊆R\mathrm{R}^2\subseteq \ Mathrm {R}R2⊆R that the relation R on set A has transitivity

Common conclusions:

The relation on set A is symmetric and antisymmetric. Try to specify the structure of relation R — IA\mathrm{I}_{\mathrm{A}}IA

If there are n elements in A, how many of them are symmetric and antisymmetric? 2n2^{\mathrm{n}}2n

Summary of the nature of the relationship:

Closure of relation: the reflexive closure, symmetric closure and transitive closure of R are denoted as R (R), S (R), t(R) respectively, also known as R, S, t for closure operations. After acting on relation R, they generate the smallest reflexive, symmetric and transitive relation including R.

Equivalence relation: if R has reflexivity, symmetry and transitivity, R is said to be an equivalence relation

Equivalence class

1.2.7 theorem:

Divided into:

Quotient set: Let R be the equivalence relation on the non-empty set A, and the set formed with all the different equivalence classes of R as elements is called the quotient set of A with respect to R, abbreviated as the quotient set of A, denoted as A/R

Equivalence relation => Quotient set:

Quotient set => equivalence relation:

Theorem 1.2.8: Let A be A non-empty set.

(1) Let R be any equivalent relation on A, then the quotient set A/R corresponding to R is A partition of A.

(2) set C as A President of A division, the Rc \ mathrm {R} _ {\ mathrm {C}} Rc = {(x, y) | x, y ∈ \ ∈ a. and in x, y, belong to the same partition C} block, the Rc \ mathrm {R} _ {\ mathrm {C}} Rc for equivalence relation on A

The second Stirling number:

How many different ways can you put n different balls into r identical boxes, and have no empty boxes? N ⩾ geqslant⩾r is required.

The different number of releasing methods is the different number of dividing n-element set A into R blocks.

(1) Special value:

(2) Recursive formula:

Subtraction: Let C and C’ both be partitions of set A. if each partition block of C is contained in A partition block of C’, then C is said to be the subtraction of C’.

C is C ‘add fine if and only if \ mathrm {R} _ {\ mathrm {C}} $$$$\ \ subseteq mathrm {R} _ {\’ mathrm {C}}

Comprehensive examples:

Partial order relation:

Reflexivity, antisymmetry, transitivity

Poset (semi-ordered set, partially ordered set). Let’s call it (A, R).

Do “or less”

Haas figure:

Chain:

For any x, y ∈\in∈A, x is comparable to y if x≤y, or y≤x

A subset of a partially ordered set in which any two elements are comparable is called a chain

Fully ordered set: A partially ordered set (A, ≤) is said to be A fully ordered set if (A, ≤) is itself A chain

Quasi order relation:

Antireflexive, antisymmetric, transitive

Max (min) element Max (min) element: finds only from a given set

The upper (lower) bound, the upper (lower) definite bound: find from the whole

Upper (lower) bound: Find the upper (lower) bound of all upper (lower) bounds closest to the desired set.

Upper and lower bounds may not exist, and when they do, they may not be unique.

Even if there are upper and lower bounds, the minimum upper bounds and the maximum lower bounds do not necessarily exist.

Reflected beam

Mapping: Suppose A and B are two sets. If for each element A of A, A definite element B of B is specified to correspond to it, the mapping is called A mapping from A to B

This mapping is denoted as σ\mathrm{\sigma}σ, then for any A ∈ in∈A, if σ\ Mathrm {\sigma}σ(a)= B, then B represents the element corresponding to A in B, b is called the image of A, and A is called the pre-image of B.

Surjective: Let sigma \mathrm{\sigma} sigma be A mapping from A to B if every element of B must be A reflection of an element of A.

All elements in B are pointed at by arrows.

In particular, A mapping from A to A is called A transformation

Injective: Set sigma \ mathrm {\ sigma} sigma is A mapping from A to B, if for any ∈ \ in ∈ a. A, B ∈ \ in ∈ A indicates \ nw-trending  = A and B, have sigma \ mathrm sigma (A) indicates \ {\ sigma} ne  = sigma \ mathrm {\ sigma} sigma (B), Say sigma \mathrm{\sigma} sigma is injective from A to B

In plain English: elements in B can have at most one arrow pointing to them.

Note: injective is not necessarily surjective; Surjective is not necessarily injective

1-1 mapping (bijective) : both surjective and injective.

The inverse mapping

Mapping of product: sigma ⋅ tau tau = ∗ sigma \ mathrm {\ sigma} \ cdot \ mathrm {\ tau} = \ mathrm \ {\ tau} * mathrm {\ sigma} sigma ⋅ tau tau = ∗ sigma instead (order)

Cardinality of a set: the number of elements (potential, concentration) of a finite set. The cardinality of A set of | | A

1-1 mapping, said the base of A and B are the same, also known as A and B equivalent (such as potential, such as strong), notes for | | | = | B

Write the base of natural number set for ℵ 0 \ aleph _0 ℵ 0 (pronounced aleph zero), then to go against the natural number set of peer set A, its base | A | = ℵ 0 \ aleph _0 ℵ 0

If A certain subset of A and B have 1-1 corresponding relation, the | | A ⩽ \ leqslant ⩽ | | B; If A certain subset of A and B have 1-1 corresponding relation, and 1-1 A and B there is no corresponding relation, the | A | < | | B

Countable sets:

A set is countable if it has a finite number of elements or if there is a 1-1 mapping between it and the set of natural numbers. Otherwise, the set is called uncountable. A countable set that does not have a finite number of elements is called countably infinite.

Theorem 1.3.2: A subset of a countable set remains a countable set. Theorem 1.3.3: Let A, B be A countable set and A∩B= ∅\varnothing∅, then A∪B is A countable set

Theorem 1.3.4: Let A and B be countable infinite sets, then A ×\times×B is countable sets.

Common conclusions:

The set Q of rational numbers is countable

The set of integers Z is countably infinite

Countable The union of infinitely many countable sets is a countable set.

Uncountable sets:

Theorem 1.3.5: The set of all real numbers is uncountable

Corollary: the set of real numbers R, interval (a,+ ∞\infty∞), [a,b], [a,b), (a,b], where a≠b, are uncountable and idenically dense with the interval (0,1).

Write the cardinality of the set of real numbers in the interval (0,1) as c, also as ℵ1\aleph _1ℵ1. Namely, c = ℵ 1 \ aleph _1 ℵ 1

The union of countable (infinitely many) sets of cardinality C remains cardinality C