実数 $R$ 上の二項関係 $\rho_1, \rho_2, \rho_3, \rho_4$ が以下のように定義されている。 $G(\rho_1) = \{(x, y) | x \geq 0, y \geq 0\}$ $G(\rho_2) = \{(x, y) | x \leq y\}$ $G(\rho_3) = \{(x, y) | (x - y)(x + y - 1) = 0\}$ $G(\rho_4) = \{(x, y) | (x - y)(x - y + 1)(x - y - 1) = 0\}$ これらの二項関係が、反射律、対称律、推移律、反対称律のうち、どれを満たしているかを判定する。

離散数学二項関係関係の性質反射律対称律推移律反対称律
2025/7/13

1. 問題の内容

実数 RR 上の二項関係 ρ1,ρ2,ρ3,ρ4\rho_1, \rho_2, \rho_3, \rho_4 が以下のように定義されている。
G(ρ1)={(x,y)x0,y0}G(\rho_1) = \{(x, y) | x \geq 0, y \geq 0\}
G(ρ2)={(x,y)xy}G(\rho_2) = \{(x, y) | x \leq y\}
G(ρ3)={(x,y)(xy)(x+y1)=0}G(\rho_3) = \{(x, y) | (x - y)(x + y - 1) = 0\}
G(ρ4)={(x,y)(xy)(xy+1)(xy1)=0}G(\rho_4) = \{(x, y) | (x - y)(x - y + 1)(x - y - 1) = 0\}
これらの二項関係が、反射律、対称律、推移律、反対称律のうち、どれを満たしているかを判定する。

2. 解き方の手順

各関係 ρi\rho_i について、それぞれの性質を調べる。
* 反射律: 任意の xRx \in R に対して (x,x)G(ρi)(x, x) \in G(\rho_i) が成り立つか。
* 対称律: 任意の x,yRx, y \in R に対して (x,y)G(ρi)(x, y) \in G(\rho_i) ならば (y,x)G(ρi)(y, x) \in G(\rho_i) が成り立つか。
* 推移律: 任意の x,y,zRx, y, z \in R に対して (x,y)G(ρi)(x, y) \in G(\rho_i) かつ (y,z)G(ρi)(y, z) \in G(\rho_i) ならば (x,z)G(ρi)(x, z) \in G(\rho_i) が成り立つか。
* 反対称律: 任意の x,yRx, y \in R に対して (x,y)G(ρi)(x, y) \in G(\rho_i) かつ (y,x)G(ρi)(y, x) \in G(\rho_i) ならば x=yx = y が成り立つか。
**ρ1\rho_1 について**
* 反射律: x0x \geq 0 ならば (x,x)G(ρ1)(x, x) \in G(\rho_1) となるためには x0x \geq 0 でなければならない。しかし、x<0x < 0 の場合も考えられるので、反射律は満たさない。
* 対称律: (x,y)G(ρ1)(x, y) \in G(\rho_1) ならば x0x \geq 0 かつ y0y \geq 0 である。このとき (y,x)G(ρ1)(y, x) \in G(\rho_1) となるためには y0y \geq 0 かつ x0x \geq 0 でなければならない。これは常に成り立つので、対称律を満たす。
* 推移律: (x,y)G(ρ1)(x, y) \in G(\rho_1) ならば x0x \geq 0 かつ y0y \geq 0 であり、(y,z)G(ρ1)(y, z) \in G(\rho_1) ならば y0y \geq 0 かつ z0z \geq 0 である。このとき (x,z)G(ρ1)(x, z) \in G(\rho_1) となるためには x0x \geq 0 かつ z0z \geq 0 でなければならない。これは常に成り立つので、推移律を満たす。
* 反対称律: (x,y)G(ρ1)(x, y) \in G(\rho_1) かつ (y,x)G(ρ1)(y, x) \in G(\rho_1) ならば x0x \geq 0 かつ y0y \geq 0 かつ y0y \geq 0 かつ x0x \geq 0 である。x=yx = y とは限らないので、反対称律は満たさない。
**ρ2\rho_2 について**
* 反射律: 任意の xRx \in R に対して xxx \leq x は常に成り立つので、反射律を満たす。
* 対称律: xyx \leq y ならば yxy \leq x とは限らないので、対称律は満たさない。
* 推移律: xyx \leq y かつ yzy \leq z ならば xzx \leq z なので、推移律を満たす。
* 反対称律: xyx \leq y かつ yxy \leq x ならば x=yx = y なので、反対称律を満たす。
**ρ3\rho_3 について**
* 反射律: (xx)(x+x1)=0(2x1)=0(x - x)(x + x - 1) = 0 \cdot (2x - 1) = 0 なので、反射律を満たす。
* 対称律: (x,y)G(ρ3)(x, y) \in G(\rho_3) ならば (xy)(x+y1)=0(x - y)(x + y - 1) = 0 である。(y,x)G(ρ3)(y, x) \in G(\rho_3) となるためには (yx)(y+x1)=0(y - x)(y + x - 1) = 0 でなければならない。
(xy)(x+y1)=0(x - y)(x + y - 1) = 0 のとき、x=yx = y または x+y=1x + y = 1 である。
x=yx = y のとき、(yx)(y+x1)=0(y - x)(y + x - 1) = 0 は成り立つ。
x+y=1x + y = 1 のとき、(yx)(y+x1)=(yx)(11)=0(y - x)(y + x - 1) = (y - x)(1 - 1) = 0 は成り立つ。
したがって、対称律を満たす。
* 推移律: (x,y)G(ρ3)(x, y) \in G(\rho_3) かつ (y,z)G(ρ3)(y, z) \in G(\rho_3) とする。
(xy)(x+y1)=0(x - y)(x + y - 1) = 0 かつ (yz)(y+z1)=0(y - z)(y + z - 1) = 0 である。
x=yx = y かつ y=zy = z ならば x=zx = z である。このとき (xz)(x+z1)=(xx)(x+x1)=0(x - z)(x + z - 1) = (x - x)(x + x - 1) = 0 となり、(x,z)G(ρ3)(x, z) \in G(\rho_3) となる。
x=yx = y かつ y+z=1y + z = 1 ならば x+z=1x + z = 1 である。このとき (xz)(x+z1)=(xz)(11)=0(x - z)(x + z - 1) = (x - z)(1 - 1) = 0 となり、(x,z)G(ρ3)(x, z) \in G(\rho_3) となる。
x+y=1x + y = 1 かつ y=zy = z ならば x+z=1x + z = 1 である。このとき (xz)(x+z1)=(xz)(11)=0(x - z)(x + z - 1) = (x - z)(1 - 1) = 0 となり、(x,z)G(ρ3)(x, z) \in G(\rho_3) となる。
x+y=1x + y = 1 かつ y+z=1y + z = 1 ならば x+y=y+zx + y = y + z より x=zx = z となる。したがって、(xz)(x+z1)=0(x - z)(x + z - 1) = 0 となるので、推移律を満たす。
* 反対称律: (x,y)G(ρ3)(x, y) \in G(\rho_3) かつ (y,x)G(ρ3)(y, x) \in G(\rho_3) とする。
(xy)(x+y1)=0(x - y)(x + y - 1) = 0 かつ (yx)(y+x1)=0(y - x)(y + x - 1) = 0 である。
したがって、x=yx = y または x+y=1x + y = 1 である。y=xy = x または y+x=1y + x = 1 である。
よって、反対称律を満たすとは限らない。
**ρ4\rho_4 について**
* 反射律: (xx)(xx+1)(xx1)=01(1)=0(x - x)(x - x + 1)(x - x - 1) = 0 \cdot 1 \cdot (-1) = 0 なので、反射律を満たす。
* 対称律: (x,y)G(ρ4)(x, y) \in G(\rho_4) ならば (xy)(xy+1)(xy1)=0(x - y)(x - y + 1)(x - y - 1) = 0 である。(y,x)G(ρ4)(y, x) \in G(\rho_4) となるためには (yx)(yx+1)(yx1)=0(y - x)(y - x + 1)(y - x - 1) = 0 でなければならない。
(xy)(xy+1)(xy1)=0(x - y)(x - y + 1)(x - y - 1) = 0 ならば、x=yx = y または x=y1x = y - 1 または x=y+1x = y + 1 である。
x=yx = y のとき、(yx)(yx+1)(yx1)=0(y - x)(y - x + 1)(y - x - 1) = 0 は成り立つ。
x=y1x = y - 1 のとき、(yx)(yx+1)(yx1)=(1)(2)(0)=0(y - x)(y - x + 1)(y - x - 1) = (1)(2)(0) = 0 は成り立つ。
x=y+1x = y + 1 のとき、(yx)(yx+1)(yx1)=(1)(0)(2)=0(y - x)(y - x + 1)(y - x - 1) = (-1)(0)(-2) = 0 は成り立つ。
したがって、(yx)(yx+1)(yx1)=0(y - x)(y - x + 1)(y - x - 1) = 0 が成り立つので、対称律を満たす。
* 推移律: 反例として、x=0,y=1,z=2x = 0, y = 1, z = 2 を考える。
(x,y)G(ρ4)(x, y) \in G(\rho_4) より、(01)(01+1)(011)=(1)(0)(2)=0(0 - 1)(0 - 1 + 1)(0 - 1 - 1) = (-1)(0)(-2) = 0 である。
(y,z)G(ρ4)(y, z) \in G(\rho_4) より、(12)(12+1)(121)=(1)(0)(2)=0(1 - 2)(1 - 2 + 1)(1 - 2 - 1) = (-1)(0)(-2) = 0 である。
(x,z)G(ρ4)(x, z) \in G(\rho_4) を確かめると、(02)(02+1)(021)=(2)(1)(3)=60(0 - 2)(0 - 2 + 1)(0 - 2 - 1) = (-2)(-1)(-3) = -6 \neq 0 である。
したがって、推移律を満たさない。
* 反対称律: (x,y)G(ρ4)(x, y) \in G(\rho_4) かつ (y,x)G(ρ4)(y, x) \in G(\rho_4) とする。
(xy)(xy+1)(xy1)=0(x - y)(x - y + 1)(x - y - 1) = 0 かつ (yx)(yx+1)(yx1)=0(y - x)(y - x + 1)(y - x - 1) = 0 である。
したがって、x=yx = y または x=y1x = y - 1 または x=y+1x = y + 1 であり、y=xy = x または y=x1y = x - 1 または y=x+1y = x + 1 である。
よって、x=yx = y または x=y+1=x1+1=xx = y + 1 = x - 1 + 1 = x または x=y1=x+11=xx = y - 1 = x + 1 - 1 = x なので、反対称律を満たさない。

3. 最終的な答え

* ρ1\rho_1: 対称律、推移律
* ρ2\rho_2: 反射律、推移律、反対称律
* ρ3\rho_3: 反射律、対称律、推移律
* ρ4\rho_4: 反射律、対称律

「離散数学」の関連問題

与えられた数字1, 1, 2, 2, 3, 3を使って6桁の整数を作る。 (1) このような整数は何通りあるか。 (2) 220000より大きいものは何通りあるか。

順列組み合わせ場合の数数え上げ
2025/7/24

全体集合 $X = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ の部分集合 $A$, $B$ について、以下の条件が与えられています。 * $\overline{A \cup ...

集合集合演算ド・モルガンの法則
2025/7/24

全体集合 $X = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ の部分集合 $A, B$ が、以下の条件を満たすとき、集合 $A, B$ と $n(\overline{A \c...

集合集合演算ド・モルガンの法則
2025/7/24

全体集合 $U = \{x | x は 10 以下の正の整数\}$、部分集合 $A = \{x | x は 2 の倍数\}$、$B = \{x | x は 3 の倍数\}$、$C = \{x | x ...

集合集合演算補集合和集合積集合
2025/7/24

集合 $A = \{x | x < -1, 4 < x\}$、集合 $B = \{x | x \le -3, 2 \le x\}$ が与えられたとき、以下の集合を求める問題です。 (1) $A \ca...

集合集合演算補集合和集合共通部分
2025/7/24

全体集合 $U = \{x | x \text{は10以下の正の整数}\}$、集合 $A = \{1, 3, 5, 6, 10\}$、集合 $B = \{2, 3, 6, 8\}$ が与えられたとき、...

集合集合演算共通部分和集合補集合
2025/7/24

問題文は、集合、順列、円順列、重複順列、組合せ、同じものを含む順列に関する8つの小問から構成されています。

集合順列円順列重複順列組合せ同じものを含む順列場合の数数え上げ
2025/7/24

与えられた順列 $(4, 2, 5, 1, 3)$ に対して、隣接する要素の入れ替え(互換)を繰り返し行うことで、順列 $(1, 2, 3, 4, 5)$ に並び替える問題です。必要な互換の回数を求め...

順列互換ソートアルゴリズム
2025/7/24

右図のような道において、以下の問いに答えます。 (1) AからBまでの最短経路は何通りあるか。 (2) AからBまでの最短経路のうち、Pを通らないものは何通りあるか。

組み合わせ最短経路場合の数
2025/7/24

「たいいくたいかい」の8文字を1列に並べる。 (1) 異なる並べ方は何通りあるか。 (2) 「く」、「か」がこの順にある並べ方は何通りあるか。 (3) 2つの「た」が隣り合わない並べ方は何通りあるか。

順列組み合わせ場合の数重複順列
2025/7/24