Basics of relations関係かんけい

1Introduction

The central question for a relation関係かんけい is whether connections between objects対象たいしょう can be recorded by choosing which ordered pairs順序対じゅんじょつい to include. A relation is not a vague word; it is a subset部分集合ぶぶんしゅうごう of a Cartesian product直積集合ちょくせきしゅうごう.

This definition lets statements that look different, such as “$$a$$a equals $$b$$b,” “$$a$$a is below $$b$$b,” “$$a$$a divides $$b$$b,” and “$$a$$a and $$b$$b have the same remainder when divided by a fixed positive integer $$m$$m,” be treated in the same form形式けいしき.

Once these statements are formalized, their properties can be determined by which ordered pairs順序対じゅんじょつい are included rather than by differences in wording. The same set-theoretic viewpoint will be used below to test reflexivity, symmetry, antisymmetry, and transitivity.

2Terms and definitions

For sets集合しゅうごう $$A,B$$A,B, a relation関係かんけい from $$A$$A to $$B$$B is a subset部分集合ぶぶんしゅうごう of $$A\times B$$A\times B.

When $$(a,b)\in R$$(a,b)\in R, we say that $$a$$a is related to $$b$$b by $$R$$R, and often write

When $$A=B$$A=B, a relation $$R\subseteq A\times A$$R\subseteq A\times A is called a binary relation二項関係にこうかんけい on $$A$$A. Equivalence relations同値関係どうちかんけい and order relations順序関係じゅんじょかんけい are special kinds of binary relations.

3Strategy

When studying a relation関係かんけい, first identify the ambient Cartesian product直積集合ちょくせきしゅうごう. Then identify which ordered pairs順序対じゅんじょつい are included.

To prove a property性質せいしつ, check that the condition holds for all relevant elements元げん. One example cannot prove reflexivity反射性はんしゃせい or transitivity推移性すいいせい. To show failure, one counterexample反例はんれい is enough.

To prove a universal condition全称条件ぜんしょうじょうけん, begin with arbitrary elements. To show that a property fails, exhibit one ordered pair順序対じゅんじょつい or tuple that violates its condition.

4Intuitive explanation

A relation関係かんけい can be viewed as marking cells in a table. Each ordered pair順序対じゅんじょつい $$(a,b)$$(a,b) in $$A\times B$$A\times B corresponds to the cell at row $$a$$a and column列れつ $$b$$b. The relation $$R$$R is the set of cells judged to hold.

Changing a relation means changing which ordered pairs are included. As long as the ambient product $$A\times B$$A\times B is fixed, the type is preserved: first components come from $$A$$A and second components come from $$B$$B.

The table viewpoint also prepares for later operations: an inverse relation逆関係ぎゃくかんけい swaps rows and columns, while composition合成ごうせい of relations follows a connection through an intermediate element元げん.

5Important properties性質せいしつ

For a binary relation二項関係にこうかんけい $$R$$R on $$A$$A, consider the following properties性質せいしつ. In the table, $$a,b,c$$a,b,c denote arbitrary elements元げん of $$A$$A.

Symmetry対称性たいしょうせい and antisymmetry反対称性はんたいしょうせい have similar names, but their meanings are not opposites.

They may hold simultaneously, and they may also both fail. Equality is a standard example satisfying both, so their names alone should not be used to treat them as opposite properties.

6Worked example: check the divisibility relation整除関係せいじょかんけい

6.1Problem

On $$A=\{1,2,3,6\}$$A=\{1,2,3,6\}, define a relation関係かんけい $$R$$R by letting $$aRb$$aRb mean “$$a$$a divides $$b$$b.” Check that $$R$$R satisfies reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, and transitivity推移性すいいせい.

6.2Explanation

For reflexivity反射性はんしゃせい, every $$a\in A$$a\in A satisfies $$a=a·1$$a=a\cdot1, so $$a$$a divides itself. Hence $$aRa$$aRa.

For antisymmetry反対称性はんたいしょうせい, suppose $$aRb$$aRb and $$bRa$$bRa. Then there are positive integers整数せいすう $$k,\ell$$k,\ell such that $$b=ak$$b=ak and $$a=b\ell$$a=b\ell. Hence $$a=ak\ell$$a=ak\ell. Since $$a\in A$$a\in A, $$a\ne 0$$a\ne0, so dividing by $$a$$a gives $$1=k\ell$$1=k\ell. Because $$k,\ell$$k,\ell are positive integers, $$k=\ell =1$$k=\ell=1, and therefore $$a=b$$a=b.

For transitivity推移性すいいせい, suppose $$aRb$$aRb and $$bRc$$bRc. Then $$b=ak$$b=ak and $$c=b\ell$$c=b\ell. Thus $$c=a\left(k\ell \right)$$c=a(k\ell), so $$aRc$$aRc.

7How to identify it and related links

• If the question is whether $$a$$a and $$b$$b are connected, think of a relation関係かんけい.
• If objects in the same set集合しゅうごう are compared, think of a binary relation二項関係にこうかんけい.
• If objects are grouped into classes, suspect an equivalence relation同値関係どうちかんけい.
• If objects are compared by size or order, suspect an order relation順序関係じゅんじょかんけい.

8Exercise links