集合と命題

集合の記号と演算、必要条件・十分条件、対偶や背理法による証明を学びます。

集合と要素

「10 以下の正の偶数の全体」のように、範囲がはっきりしたものの集まりを集合といい、集合に属する1つ1つのものを要素といいます。 $a$ が集合 $A$ の要素であることを $a \in A$ 、要素でないことを $a \notin A$ と書きます。

集合の表し方は2通りあります。要素を書き並べる方法と、要素の満たす条件を書く方法です。たとえば「10 以下の正の偶数の全体」の集合 $A$ は

A = \{2, 4, 6, 8, 10\}

とも書けますし、「 $x$ は 10 以下の正の偶数」という条件を縦棒 $\mid$ の右に書く形式でも表せます。たとえば $\{x \mid 1 \le x \le 5\}$ は「 $1 \le x \le 5$ を満たす $x$ 全体の集合」を表します。

部分集合と集合の相等

集合 $A$ のどの要素も集合 $B$ の要素であるとき、 $A$ は $B$ の部分集合であるといい、 $A \subset B$ と書きます。

$A \subset B$ かつ $B \subset A$ のとき、 $A$ と $B$ は等しいといい、 $A = B$ と書きます。

要素を1つももたない集合を空集合といい、 $\varnothing$ で表します。 $\varnothing$ はどんな集合の部分集合とも考えます。

次に、2つの集合から新しい集合を作る演算を学びます。考えている対象全体の集合を全体集合といい、ふつう $U$ で表します。

共通部分・和集合・補集合

共通部分 $A \cap B$ … $A$ と $B$ の両方に属する要素全体の集合( $A$ かつ $B$ )

和集合 $A \cup B$ … $A$ と $B$ の少なくとも一方に属する要素全体の集合( $A$ または $B$ )

補集合 $\overline{A}$ … 全体集合 $U$ の要素のうち、 $A$ に属さない要素全体の集合

数学の「または」は「少なくとも一方」という意味で、両方に属する要素も $A \cup B$ に含まれることに注意しましょう。

例題 1

全体集合を $U = \{1, 2, 3, 4, 5, 6, 7, 8\}$ とし、 $A = \{1, 2, 4, 8\}$ 、 $B = \{2, 4, 6, 8\}$ とする。 $A \cap B$ 、 $A \cup B$ 、 $\overline{A}$ 、 $\overline{A \cup B}$ を求めよ。

解き方

両方に属する要素を拾うと

A \cap B = \{2, 4, 8\}

少なくとも一方に属する要素を集めると

A \cup B = \{1, 2, 4, 6, 8\}

$U$ から $A$ の要素を除くと

\overline{A} = \{3, 5, 6, 7\}

$U$ から $A \cup B$ の要素を除くと

\overline{A \cup B} = \{3, 5, 7\}

要素を書き並べて数え上げるだけですが、書き落とし・重複がないか必ず見直しましょう。

ド・モルガンの法則

\overline{A \cup B} = \overline{A} \cap \overline{B}

\overline{A \cap B} = \overline{A} \cup \overline{B}

「和集合の補集合は補集合の共通部分」「共通部分の補集合は補集合の和集合」。補集合をとると $\cup$ と $\cap$ が入れかわる、と覚えましょう。ベン図をかいて、両辺が同じ部分を表すことを自分の手で確認しておくと忘れません。

例題 1 で確認してみると、 $\overline{A} = \{3, 5, 6, 7\}$ 、 $\overline{B} = \{1, 3, 5, 7\}$ なので $\overline{A} \cap \overline{B} = \{3, 5, 7\}$ となり、確かに $\overline{A \cup B}$ と一致しています。

命題と条件

「 $\sqrt{2}$ は無理数である」のように、正しいか正しくないかがはっきり定まる文や式を命題といいます。正しい命題を真、正しくない命題を偽といいます。

文字 $x$ を含む文「 $x > 3$ 」は、 $x$ の値が決まるとはじめて真偽が定まります。このような文を $x$ に関する条件といいます。2つの条件 $p$ 、 $q$ について、「 $p$ ならば $q$ 」という形の命題を $p \Longrightarrow q$ と書き、 $p$ を仮定、 $q$ を結論といいます。

命題の真偽と反例

命題 $p \Longrightarrow q$ が真であるとは、 $p$ を満たすものがすべて $q$ を満たすことです。

偽であることを示すには、 $p$ を満たすのに $q$ を満たさない例(反例)を1つ挙げれば十分です。

条件 $p$ 、 $q$ を満たすもの全体の集合をそれぞれ $P$ 、 $Q$ とすると、 $p \Longrightarrow q$ が真であることと $P \subset Q$ が成り立つことは同じです。命題の真偽は集合の包含関係で考えられるのです。

例題 2

$x$ は実数とする。次の命題の真偽を調べよ。偽のときは反例を挙げよ。
(1) $x = 2 \Longrightarrow x^2 = 4$
(2) $x^2 = 4 \Longrightarrow x = 2$

解き方

(1) $x = 2$ ならば $x^2 = 2^2 = 4$ なので、真です。

(2) $x^2 = 4$ を満たす $x$ は $x = 2$ と $x = -2$ の2つあります。 $x = -2$ は $x^2 = 4$ を満たすのに $x = 2$ ではないので、反例です。よってこの命題は偽です。

集合で見ると、(2) は $\{-2, 2\} \subset \{2\}$ が成り立たない、ということです。「2乗をはずすと符号が2通り」は反例探しの定番ポイントです。

必要条件・十分条件

命題 $p \Longrightarrow q$ が真であるとき

$p$ は $q$ であるための十分条件

$q$ は $p$ であるための必要条件

といいます。さらに $p \Longrightarrow q$ と $q \Longrightarrow p$ がともに真であるとき、 $p$ は $q$ であるための必要十分条件であるといい、 $p \Longleftrightarrow q$ と書きます。このとき $p$ と $q$ は同値であるといいます。

覚え方は「矢印の出発点(根元)が十分条件、矢印の行き先(先端)が必要条件」です。集合でいえば、 $P \subset Q$ のとき小さい方 $P$ の条件が十分条件、大きい方 $Q$ の条件が必要条件になります。「十分条件は条件として強い(範囲がせまい)、必要条件は弱い(範囲が広い)」というイメージをもつと迷いにくくなります。

必要条件か十分条件かを判定するときは、必ず $p \Longrightarrow q$ と $q \Longrightarrow p$ の両方向の真偽を調べます。

例題 3

$x$ は実数とする。「 $x = 1$ 」は「 $x^2 = 1$ 」であるための何条件か。

解き方

両方向の真偽を調べます。

「 $x = 1 \Longrightarrow x^2 = 1$ 」は真です。

「 $x^2 = 1 \Longrightarrow x = 1$ 」は、反例 $x = -1$ があるので偽です。

よって、 $x = 1$ は $x^2 = 1$ であるための十分条件ですが、必要条件ではありません。答えは「十分条件であるが必要条件ではない」です。

集合で見ると $\{1\} \subset \{-1, 1\}$ で、せまい方の条件 $x = 1$ が十分条件になっています。

逆・裏・対偶と対偶を利用した証明

条件 $p$ に対して、「 $p$ でない」という条件を $p$ の否定といい、 $\overline{p}$ と書きます。命題 $p \Longrightarrow q$ に対して、仮定と結論を入れかえたり否定したりして、次の3つの命題が作れます。

逆・裏・対偶

命題 $p \Longrightarrow q$ に対して

逆: $q \Longrightarrow p$ (仮定と結論を入れかえる)

裏: $\overline{p} \Longrightarrow \overline{q}$ (両方を否定する)

対偶: $\overline{q} \Longrightarrow \overline{p}$ (入れかえて、両方を否定する)

もとの命題とその対偶は、真偽がつねに一致します。一方、もとの命題が真でも、逆や裏は真とは限りません。

たとえば真の命題「 $x = 1 \Longrightarrow x^2 = 1$ 」の逆「 $x^2 = 1 \Longrightarrow x = 1$ 」は偽でした(反例 $x = -1$ )。逆や裏を「当然成り立つ」と思い込むのは典型的な誤りなので注意しましょう。

なお、対偶と真偽が一致する理由は集合で考えるとわかります。 $P \subset Q$ ならば、 $Q$ の外にあるものは必ず $P$ の外にある、つまり $\overline{Q} \subset \overline{P}$ が成り立つからです。

「かつ」「または」の否定

条件の否定を作るときは、ド・モルガンの法則に対応する次の規則を使います。

「 $p$ かつ $q$ 」の否定は「 $\overline{p}$ または $\overline{q}$ 」

「 $p$ または $q$ 」の否定は「 $\overline{p}$ かつ $\overline{q}$ 」

また、不等式の否定では等号の有無が入れかわります。たとえば「 $x > 3$ 」の否定は「 $x \le 3$ 」です。

対偶ともとの命題の真偽が一致することを利用すると、直接証明しにくい命題を、対偶を証明することで示せます。結論が「〜でない」という否定の形をしているとき、対偶を作ると仮定が肯定的な使いやすい形になることが多く、特に有効です。

例題 4(対偶を利用した証明)

整数 $n$ について、 $n^2$ が偶数ならば $n$ は偶数であることを証明せよ。

解き方

もとの命題は「 $n^2$ が偶数 $\Longrightarrow$ $n$ が偶数」です。仮定の「 $n^2$ が偶数」から直接 $n$ の情報を取り出すのは難しいので、対偶

「 $n$ が奇数 $\Longrightarrow$ $n^2$ が奇数」

を証明します。 $n$ が奇数のとき、整数 $k$ を用いて $n = 2k + 1$ と表せます。このとき

n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

$2k^2 + 2k$ は整数なので、 $n^2$ は奇数です。よって対偶は真であり、もとの命題も真です。(証明終)

「偶数は $2k$ 、奇数は $2k+1$ と文字でおいて計算する」のが整数の証明の基本です。最後に「 $2 \times m + 1$ ( $m$ は整数)の形になった」ことを明記しましょう。

背理法

背理法は、「命題が成り立たないと仮定すると、矛盾が起こる。だから命題は成り立つ」という論法です。結論を直接導くのではなく、結論を否定してみて話のつじつまが合わなくなることを示します。

背理法の手順

1. 証明したい結論を否定した仮定を立てる

2. その仮定のもとで議論を進め、矛盾(仮定や既知の事実と食い違うこと)を導く

3. 矛盾が生じたのは最初の仮定が誤りだったからである、と結論づける

「〜は無理数である」「〜でない」「少なくとも1つは〜」のような、直接示しにくい形の命題に特に有効です。

背理法の代表例が「 $\sqrt{2}$ は無理数である」ことの証明です。無理数とは「有理数でない実数」のことなので、「 $\sqrt{2}$ は有理数である」と仮定して矛盾を導きます。有理数は整数 $p$ 、 $q$ を用いて分数 $\dfrac{p}{q}$ の形に表せる数であることを思い出しておきましょう。

例題 5(背理法の代表例)

$\sqrt{2}$ が無理数であることを証明せよ。ただし、整数 $n$ について「 $n^2$ が偶数ならば $n$ は偶数である」ことは使ってよい。

解き方

$\sqrt{2}$ が有理数であると仮定します。すると、互いに素な(1以外の公約数をもたない)正の整数 $p$ 、 $q$ を用いて

\sqrt{2} = \frac{p}{q}

と表せます。両辺を $q$ 倍して2乗すると

p^2 = 2q^2

右辺は偶数なので $p^2$ は偶数、したがって $p$ は偶数です。そこで $p = 2k$ ( $k$ は正の整数)とおくと

(2k)^2 = 2q^2

すなわち $4k^2 = 2q^2$ 、両辺を $2$ で割って

q^2 = 2k^2

よって $q^2$ は偶数、したがって $q$ も偶数です。すると $p$ と $q$ はともに偶数となり、公約数 $2$ をもつことになって、「互いに素」という仮定に矛盾します。

したがって、 $\sqrt{2}$ は有理数ではなく、無理数です。(証明終)

「互いに素」と最初におくのがポイントです。この設定があるからこそ、「両方とも偶数」が矛盾になります。

対偶を利用した証明と背理法はどちらも「間接証明法」です。使い分けの目安は、命題が「 $p$ ならば $q$ 」の形なら対偶、そうでない形(「〜は無理数である」など)や、結論の否定から豊富な情報が引き出せるときは背理法、と考えるとよいでしょう。

§1集合と要素

§2命題と条件

§3逆・裏・対偶と対偶を利用した証明

§4背理法

集合と要素

命題と条件

逆・裏・対偶と対偶を利用した証明

背理法