You get a bonus - 1 coin for daily activity. Now you have 1 coin

Binary relation Bijection. Surgery. Injection

Lecture



Binary relation in mathematics is a two-place relationship between any two sets Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection , that is, every subset of the Cartesian product of these sets: Binary relation  Bijection. Surgery.  Injection [1] . Binary relation on set Binary relation  Bijection. Surgery.  Injection - any subset Binary relation  Bijection. Surgery.  Injection Such binary relations are most often used in mathematics, in particular, such are equality, inequality, equivalence, order relation.

Related Definitions

The set of all the first elements of pairs from Binary relation  Bijection. Surgery.  Injection called the domain definition area Binary relation  Bijection. Surgery.  Injection and is denoted as Binary relation  Bijection. Surgery.  Injection .

Binary relation  Bijection. Surgery.  Injection

  • The set of all second pairs of elements from Binary relation  Bijection. Surgery.  Injection is called a relationship value area Binary relation  Bijection. Surgery.  Injection and is denoted by Binary relation  Bijection. Surgery.  Injection .

Binary relation  Bijection. Surgery.  Injection

  • Inversion (inverse relationship) Binary relation  Bijection. Surgery.  Injection - it's a lot Binary relation  Bijection. Surgery.  Injection and is denoted as Binary relation  Bijection. Surgery.  Injection .
  • Composition (superposition) of binary relations Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection - it's a lot Binary relation  Bijection. Surgery.  Injection and is denoted as Binary relation  Bijection. Surgery.  Injection .

Relationship Properties

Binary relation Binary relation  Bijection. Surgery.  Injection on some set Binary relation  Bijection. Surgery.  Injection may have different properties, for example:

  • reflexivity: Binary relation  Bijection. Surgery.  Injection ,
  • anti-reflexivity (irreflexivity): Binary relation  Bijection. Surgery.  Injection ,
  • coreflexivity: Binary relation  Bijection. Surgery.  Injection ,
  • symmetry: Binary relation  Bijection. Surgery.  Injection ,
  • antisymmetry: Binary relation  Bijection. Surgery.  Injection ,
  • asymmetry: Binary relation  Bijection. Surgery.  Injection is equivalent to the simultaneous anti-reflexivity and antisymmetry of the relationship,
  • transitivity: Binary relation  Bijection. Surgery.  Injection ,
  • Euclidean: Binary relation  Bijection. Surgery.  Injection ,
  • completeness (or connectivity [2] ): Binary relation  Bijection. Surgery.  Injection ,
  • Connectivity (or weak connectivity [2] ): Binary relation  Bijection. Surgery.  Injection ,
  • connexity (born connex ): Binary relation  Bijection. Surgery.  Injection ,
  • trichotomy: Binary relation  Bijection. Surgery.  Injection exactly one of three statements is true: Binary relation  Bijection. Surgery.  Injection , Binary relation  Bijection. Surgery.  Injection or Binary relation  Bijection. Surgery.  Injection .

Types of relationships

  • A reflexive transitive relation is called a quasi-order relation.
  • A reflexive symmetric transitive relation is called an equivalence relation.
  • A reflexive antisymmetric transitive relation is called a (partial) order relation.
  • An anti-reflective antisymmetric transitive relation is called a strict order relation.
  • Full antisymmetric (for any Binary relation  Bijection. Surgery.  Injection performed Binary relation  Bijection. Surgery.  Injection or Binary relation  Bijection. Surgery.  Injection a) transitive relation is called a linear order relation.
  • An anti-reflective antisymmetric relationship is called a dominance ratio.

Types of binary relationships

  • Inverse relationship (inverse relation to Binary relation  Bijection. Surgery.  Injection ) - is a double ratio consisting of pairs of elements Binary relation  Bijection. Surgery.  Injection obtained by rearranging pairs of elements Binary relation  Bijection. Surgery.  Injection this relationship Binary relation  Bijection. Surgery.  Injection . Denoted by: Binary relation  Bijection. Surgery.  Injection . For a given relation and its inverse, the equality is true: Binary relation  Bijection. Surgery.  Injection .
  • Mutual inverse relationship (reciprocal relationship) - a relationship that is inverse to each other. The domain of one of them is the domain of the other, and the domain of the first is the domain of the other.
  • Reflexive attitude - double ratio Binary relation  Bijection. Surgery.  Injection defined on some set and characterized in that for any Binary relation  Bijection. Surgery.  Injection of this set element Binary relation  Bijection. Surgery.  Injection is in relation Binary relation  Bijection. Surgery.  Injection to oneself that is for any element Binary relation  Bijection. Surgery.  Injection of this set takes place Binary relation  Bijection. Surgery.  Injection . Examples of reflexive relations: equality, simultaneity, similarity.
  • Anti-reflective relation (irreflexive relation; just as antisymmetry does not coincide with asymmetry, irreflexivity does not coincide with non-reflexivity) - binary relation Binary relation  Bijection. Surgery.  Injection defined on some set and characterized in that for any element Binary relation  Bijection. Surgery.  Injection this set is incorrect that it is in relation Binary relation  Bijection. Surgery.  Injection to myself (wrong that Binary relation  Bijection. Surgery.  Injection ), that is, it is possible that the element of the set is not in relation Binary relation  Bijection. Surgery.  Injection to myself.
  • Transitive relationship - double ratio Binary relation  Bijection. Surgery.  Injection defined on some set and characterized by the fact that for any Binary relation  Bijection. Surgery.  Injection of Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection follows Binary relation  Bijection. Surgery.  Injection ( Binary relation  Bijection. Surgery.  Injection ). Examples of transitive relations: “more”, “less”, “equal”, “like”, “higher”, “north”.
  • Non-transitive attitude - double ratio Binary relation  Bijection. Surgery.  Injection defined on some set and characterized by the fact that for any Binary relation  Bijection. Surgery.  Injection of this set of Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection it does not follow Binary relation  Bijection. Surgery.  Injection ( Binary relation  Bijection. Surgery.  Injection ). An example of a non-transitive relationship: “x father y”
  • Symmetric relation - binary relation Binary relation  Bijection. Surgery.  Injection defined on some set and characterized in that for any elements Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection of this set of what Binary relation  Bijection. Surgery.  Injection is to Binary relation  Bijection. Surgery.  Injection in a relationship Binary relation  Bijection. Surgery.  Injection follows that and Binary relation  Bijection. Surgery.  Injection is in the same attitude Binary relation  Bijection. Surgery.  Injection - Binary relation  Bijection. Surgery.  Injection . An example of symmetric relations can be equality, equivalence relation, similarity, simultaneity.
  • Antisymmetric ratio - binary ratio Binary relation  Bijection. Surgery.  Injection defined on some set and characterized by the fact that for any Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection of Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection follows Binary relation  Bijection. Surgery.  Injection (i.e Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection performed at the same time only for equal members).
  • Asymmetric Ratio - Binary Ratio Binary relation  Bijection. Surgery.  Injection defined on some set and characterized by the fact that for any Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection of Binary relation  Bijection. Surgery.  Injection follows Binary relation  Bijection. Surgery.  Injection . Example: the relationship “more” (>) and “less” (<).
  • Equivalence relation - binary relation Binary relation  Bijection. Surgery.  Injection between objects Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection which is both reflexive, symmetric and transitive. Examples: equality, equal power of two sets, similarity, simultaneity.
  • Order relation is a relation possessing only some of the three properties of an equivalence relation: a reflexive and transitive relation, but asymmetric (for example, “not more”) forms a non-strict order, and a relation is transitive, but non-reflective and asymmetric (for example, “less”) is strict order
  • The function of one variable is a binary relation Binary relation  Bijection. Surgery.  Injection defined on some set, characterized in that each value Binary relation  Bijection. Surgery.  Injection relations Binary relation  Bijection. Surgery.  Injection only a single value matches Binary relation  Bijection. Surgery.  Injection . Relationship Feature Property Binary relation  Bijection. Surgery.  Injection written in the form of an axiom: Binary relation  Bijection. Surgery.  Injection .
  • Bijection (one-to-one relation) - binary relation Binary relation  Bijection. Surgery.  Injection defined on some set, characterized by the fact that it has every value Binary relation  Bijection. Surgery.  Injection matches a single value Binary relation  Bijection. Surgery.  Injection and each value Binary relation  Bijection. Surgery.  Injection matches a single value Binary relation  Bijection. Surgery.  Injection .
  • Bound relation - binary relation Binary relation  Bijection. Surgery.  Injection defined on some set, characterized in that for any two different elements Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection of this set, one of them is in relation Binary relation  Bijection. Surgery.  Injection to the other (that is, one of the two relations is satisfied: Binary relation  Bijection. Surgery.  Injection or Binary relation  Bijection. Surgery.  Injection ). Example: “less than” ratio (<).

Relationship Operations

Since the relations defined on a fixed pair of sets Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection the essence of a subset of a set Binary relation  Bijection. Surgery.  Injection , then the totality of all these relations forms a Boolean algebra with respect to the operations of uniting, intersecting, and complementing relations. In particular, for arbitrary Binary relation  Bijection. Surgery.  Injection , Binary relation  Bijection. Surgery.  Injection :

Binary relation  Bijection. Surgery.  Injection ,

Binary relation  Bijection. Surgery.  Injection ,

Binary relation  Bijection. Surgery.  Injection .

Often, instead of combining, intersecting and complementing relationships, they talk about their disjunction, conjunction, and denial.

For example, Binary relation  Bijection. Surgery.  Injection , Binary relation  Bijection. Surgery.  Injection , that is, the union of a strict order relation with an equality relation coincides with a nonstrict order relation, and their intersection is empty.

In addition to the above, the operations of inversion and multiplication of relations, defined as follows, are important. If a Binary relation  Bijection. Surgery.  Injection , the inverse relation is called the relation Binary relation  Bijection. Surgery.  Injection determined on pair Binary relation  Bijection. Surgery.  Injection , Binary relation  Bijection. Surgery.  Injection and consisting of those pairs Binary relation  Bijection. Surgery.  Injection for which Binary relation  Bijection. Surgery.  Injection . For example, Binary relation  Bijection. Surgery.  Injection .

Let be Binary relation  Bijection. Surgery.  Injection , Binary relation  Bijection. Surgery.  Injection . Composition (or product) of relations Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection called attitude Binary relation  Bijection. Surgery.  Injection such that:

Binary relation  Bijection. Surgery.  Injection .

For example, for a strict order relation on the set of natural numbers, its multiplication by itself is defined as follows: Binary relation  Bijection. Surgery.  Injection .

Binary relations Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection are called permutable if Binary relation  Bijection. Surgery.  Injection . For any binary relation Binary relation  Bijection. Surgery.  Injection defined on Binary relation  Bijection. Surgery.  Injection , takes place Binary relation  Bijection. Surgery.  Injection where symbol Binary relation  Bijection. Surgery.  Injection denotes equality defined on Binary relation  Bijection. Surgery.  Injection . However equality Binary relation  Bijection. Surgery.  Injection not always fair.

The following identities hold:

  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection ,
  • Binary relation  Bijection. Surgery.  Injection .

Analogs of the last two identities for the intersection of relations do not exist.

Notes

  1. Kostrikin A.I. Introduction to Algebra. Fundamentals of algebra .. - M .: Fizmatlit, 1994. - p. 47-48. - 320 s. - ISBN 5-02-014644-7.
  2. 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Multi-criteria models of the formation and selection of options for systems. - M .: Science, 1986. (p. 48)

The binary relation between two sets is the correspondence of the elements of one of them to the elements of the second.

Content

Definition Binary relation  Bijection. Surgery.  Injection

Let two sets be given Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection , let it go Binary relation  Bijection. Surgery.  Injection - A subset of their Cartesian products. Then threesome Binary relation  Bijection. Surgery.  Injection called the binary relation between Binary relation  Bijection. Surgery.  Injection and Binary relation  Bijection. Surgery.  Injection Statement Binary relation  Bijection. Surgery.  Injection usually written as Binary relation  Bijection. Surgery.  Injection and read " Binary relation  Bijection. Surgery.  Injection corresponds to Binary relation  Bijection. Surgery.  Injection " If a Binary relation  Bijection. Surgery.  Injection they write Binary relation  Bijection. Surgery.  Injection or Binary relation  Bijection. Surgery.  Injection

Relationship Types Binary relation  Bijection. Surgery.  Injection

Surgery, injection and bijection.

- The mapping f: x-> y is called a SURJECT , if Ay∈Y x∈X: y = f (x). Then y is an image, x is a preimage of y.
- The mapping f: x-> y is called INJECTION , if x 1 ≠ x 2 => f (x 1 ) ≠ f (x 2 ), those different elements of the set X are translated into different elements of the set Y.
or f (x 1 ) ≠ f (x 2 ) => x 1 = x 2
- A mapping f: x-> y is called a bijection if it is both surjective and injective. With a bijective reflection, each element of one set corresponds to exactly one element of another set, and the inverse mapping is defined, which has the same properties.

Binary relation  Bijection. Surgery.  Injection

Binary relation Binary relation  Bijection. Surgery.  Injection called

  • injective if

    Binary relation  Bijection. Surgery.  Injection

  • full left if

    Binary relation  Bijection. Surgery.  Injection

  • surjective (or full to the right) if

    Binary relation  Bijection. Surgery.  Injection

  • functional if

    Binary relation  Bijection. Surgery.  Injection

  • function if it is complete on the left and functional;
  • bijective if it is completely left and right, as well as injective and functional.

Types of relationships Binary relation  Bijection. Surgery.  Injection

  • A reflexive symmetric transitive relation is called an equivalence relation.
  • A reflexive antisymmetric transitive relation is called a (partial) order relation.

A binary relation on a set is called a partial order relation [1] if it satisfies the properties

  1. reflexivity: for all;
  2. antisymmetry: for all;
  3. transitivity: for all.

Definition A binary relation f is called a function if from Îf and Îf it follows that y = z.

Since functions are binary relations, two functions f and g are equal if they consist of the same elements. The domain of function definition is D f , and the domain of values ​​is R f . They are defined in the same way as for binary relations.

If f is a function, then instead of Îf, they write y = f (x) and say that y is the value corresponding to the argument x , or y is the image of the element x under the mapping f . In this case, x is called the prototype of the element y .

Definition We call f an n-local function from X to Y if f: X n ®Y. Then we write y = f (x 1 , x 2 , ..., x n ) and say that y is the value of the function with the values ​​of the arguments x 1 , x 2 , ..., x n .

Let f: X®Y.

Definition A function f is called injective if for any x 1 , x 2 , y from y = f (x 1 ) and y = f (x 2 ) it follows that x 1 = x 2 , that is, each value of the function corresponds to a single value of the argument.

Definition A function f is called surjective if for every element y Î Y there exists an element x Î X such that y = f (x).

Definition The function f is called bijective if f is both surjective and injective.

Figure 9 illustrates the concepts of relationships, functions, injections, surjections and bections.

Binary relation  Bijection. Surgery.  Injection


Example 9

Consider three functions defined on the set of real numbers and taking on the value in the same set:

  1. the function f (x) = e x is injective, but not surjective;
  2. the function f (x) = x 3 -x is surjective, but not injective;
  3. the function f (x) = 2x + 1 is bijective.

Well, take two sets: a lot of students and a lot of chairs in the classroom. And we will establish the correspondence between these two sets, i.e., just sit the students on the chairs.

1. If each student sits in a separate chair (some chairs may remain free), then this is an injection. It is clear that with such a display, the number of chairs cannot be less than the number of students (students cannot sit down two on one chair).

2. If all the chairs were occupied (some may have two or more students), then this is a surjection. In this case, the number of students cannot be less than the chairs.

3. If each student sits on a separate chair, and there are neither free chairs, nor students who lacked chairs, this is a bijection. That is, a bijection is both an injection (each student sits in a separate chair) and a surjection (all chairs are occupied). To be able to display such (bijection) the number of students must be exactly equal to the number of chairs.

Naturally, instead of pupils, chairs can be anything, for example, numerical sets.

All these correspondences can be established between infinite sets. And besides, between the finite and the infinite is an injection, or the infinite and the finite is a surjection.

See also


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.