« previous section   next section »


2.6  Many-argument relations

Binary relations are subsets of the Cartesian product of two sets. They are two-argument relations. n-argument realations are subsets of Cartesian product od n sets. As an example we take a three dimensional Euclidean space R3 (R × R × R), the elements of which are triplets of real numbers (x,y,z) indicating the coordinates of a point in the space.

Example 2.6.1

  1. Consider dependence between triplets of persons x, y, z, such that x  is the mother, and y is the father of z. If by X we will mark the set of  interested us persons, then the described dependence is a three-argument relation in  X.
  2. Let S be the set of first-year students of the PJIIT. After the first semester each student ought to pass four exams E1, E2, E3, E4. The results can be presented as a table, in which each row corresponds to one student, the first column contains the name of a student and the other columnes correspond to the results obtained by this student. Interdependence described in this table is a five-argument relation, see Fig. 2.6.1.

Fig. 2.6.1 An example of a many-argument relation.

Definition 2.6.1

Let X1, X2, ..., Xn be arbitrary nonempty sets, where n is a natural number. By a product of these sets we understand the set X1 × X2 × ... × Xn which consists of ordered n-tuples of the form (x1, x2, ...,xn), where xi ∈ Xi for i=1,2...,n.

Two n-tuples (x1, x2, ...,xn) and (y1, y2, ...,yn), are equal if and only if elements on the corresponding positions are equal, i.e. xi = yi, dla i =1,...n.

Thus, the Cartesian product of the family of n sets {Xi}i ×n is the collection of all ordered n-tuples that i-th position contains an element of the set Xi. This collection can be seen as constituting an n-dimensional space in which each n-tuple designates a point.

Lemma 2.6.1

If Xi has ki elements, then the Cartesian product X1 × X2 × ... × Xn has k1 * k2 *... * kn elements.

The proof of the lemma requires the induction principle. We will discuss it later. Informally, for each choice of an element from the first set one can take arbitrary elements from the other sets. For the first element we have k1 possibilities, hence the result is k1*(the number of possible (n-1)-tuples from the set z X2 ×... × Xn.

Definition 2.6.2

A subset of the set X1 × X2 × ... × Xn is called an n-argument relation (in short an n-ary relation).

When r is an n-ary relation in the product X1 × X2 × ... × Xn, then instead of (x1, x2, ..., xn) ∈ r, we will write r(x1, x2, ..., xn).

Example 2.6.2

  1. Let r be a subset of the product N × N × N such that (x,y,z) ∈ r iff x2 +y2 = z2. Thus r is a 3-ary relation in N. The triple (3,4,5) is in the relation r, (3,4,5) ∈ r, and (1,2,3) is not, (1,2,3) ∉ r.
  2. Let w be a polynomial in one variable of degree n with the real coefficients w(x) = a0 +a1*x + a2*x2...+ an*xn. We will define a relation r in the set of real numbers R as follows (a0, a1, ..., an, x, y) ∈ r iff w(x) = y. Hence r is n+3-ary relation, such that (a0, a1, ..., an, a, b) is in r if and only if b is the value of the polynomial in one variable with coefficients defined by the first n+1-elements a0, a1, ..., an, at the argument a.
  3. Let r be a 3-argument relation defined in the product R3 such that (x,y,z) ∈ r iff x<y<z. Hence, the relation holds for a triple (a,b,c) if the middle element b is grater than this to the left (i.e. a) and less than this to the right (i.e. c).

Question 2.6.1: How many ordered pairs are there at most in a binary relation defined in a 100-element set?


« previous section   next section »