Lecture
Binary relation in mathematics is a two-place relationship between any two sets and , that is, every subset of the Cartesian product of these sets: [1] . Binary relation on set - any subset Such binary relations are most often used in mathematics, in particular, such are equality, inequality, equivalence, order relation.
The set of all the first elements of pairs from called the domain definition area and is denoted as .
Binary relation on some set may have different properties, for example:
Since the relations defined on a fixed pair of sets and the essence of a subset of a set , 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 , :
,
,
.
Often, instead of combining, intersecting and complementing relationships, they talk about their disjunction, conjunction, and denial.
For example, , , 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 , the inverse relation is called the relation determined on pair , and consisting of those pairs for which . For example, .
Let be , . Composition (or product) of relations and called attitude such that:
.
For example, for a strict order relation on the set of natural numbers, its multiplication by itself is defined as follows: .
Binary relations and are called permutable if . For any binary relation defined on , takes place where symbol denotes equality defined on . However equality not always fair.
The following identities hold:
Analogs of the last two identities for the intersection of relations do not exist.
The binary relation between two sets is the correspondence of the elements of one of them to the elements of the second.
Let two sets be given and , let it go - A subset of their Cartesian products. Then threesome called the binary relation between and Statement usually written as and read " corresponds to " If a they write or
- 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 called
A binary relation on a set is called a partial order relation [1] if it satisfies the properties
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.
Example 9
Consider three functions defined on the set of real numbers and taking on the value in the same set:
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.
Comments
To leave a comment
Discrete Math. Set theory. Graph theory. Combinatorics.
Terms: Discrete Math. Set theory. Graph theory. Combinatorics.