공진리란? Vacuous Truth

수학/집합론|2019. 11. 14. 16:37


임의의 명제 $p$ 와 모순 $c$ 그리고 $A_{\alpha} \subset X$ 에 대해 다음이 성립한다.

[1] 공진리 : $c \implies p$

[2] 합집합 : $\displaystyle \bigcup_{\alpha \in \emptyset} A_{\alpha} = \emptyset$

[3] 교집합 : $\displaystyle \bigcap_{\alpha \in \emptyset} A_{\alpha} = X$


예를 들어 "신은 죽었다." 라는 말에서 신이 존재하지 않는다면, 가정부터 틀려먹었다면 어떻게 되는 걸까? 신이 존재하지 않는다면 $0$ 명의 신이 죽은 것이므로 누가 진짜 죽었나 살았나 따질 것도 없이 참이 된다. 한편 "신은 살아있다." 라는 말 역시 신이 존재하지 않는다면 $0$ 명을 확인하는 것이므로 반드시 참이다.


이렇듯 가정이 모순이라면 주장이 무엇이든 상관 없이 참이 되는 것을  공진리Vacuous Truth 혹은 항진이라고 한다. 물론 저 형태 말고도 다른 항진명제는 있지만 그 중에서 가장 받아들이기 어려운 게 $c \implies p$ 이다. 위 예시와 비슷하게 집합이 주어졌을 때 그 부분집합을 $0$ 개만큼 합집합을 취하거나 교집합을 취할 수 있다. $\displaystyle \sum_{n=0}^{0} n = 0$ 인 것을 생각해보면 조금은 받아들이기 쉬워질 것이다.



증명(공진리)

$p$ 가 참일때와 거짓일 때 모두 $c \to p$ 가 참임을 보이면 된다. $x \to y \equiv \lnot ( x \land \lnot y )$ 이므로

$$c \to p \equiv \lnot ( c \land \lnot p )$$

$p$ 가 참이든 거짓이든 $c$ 와 논리곱을 취한 결과는 거짓이므로

$$ \lnot ( c \land \lnot p ) \equiv \lnot c$$

모순 $c$ 의 부정은 항상 참이므로 $c \to p$ 는 $p$ 에 관계없이 참이다.


증명(합집합)

모든 $x \in X$ 에 대해 $\displaystyle x \notin \bigcup_{\alpha \in \emptyset} A_{\alpha} $ 임을 보이면 된다.

$$\begin{eqnarray*} x \notin \bigcup_{\alpha \in \emptyset} A_{\alpha} & \iff & \lnot \left( x \in \bigcup_{\alpha \in \emptyset} A_{\alpha} \right) \\ & \iff & \lnot ( x \in A_{\alpha_{0}} \text{ for some } \alpha_{0} \in \emptyset ) \\ &\iff &x \notin A_{\alpha} \text{ for all }  \alpha \in \emptyset \\ & \iff & \alpha \in \emptyset \to x \notin A_{\alpha} \end{eqnarray*}$$

집합 $\emptyset$ 이 원소를 가진다는 것은 공집합의 정의에 모순이므로, $\alpha \in \emptyset$ 은 거짓이다. [1] 공진리에 따라 $\alpha \in \emptyset \to x \notin A_{\alpha}$ 은 참이고 그와 동치인 $\displaystyle x \notin \bigcup_{\alpha \in \emptyset} A_{\alpha} $ 도 참이다.


증명(교집합)

모든 $x \in X$ 에 대해 $\displaystyle x \in \bigcap_{\alpha \in \emptyset} A_{\alpha} $ 임을 보이면 된다.

$$\begin{eqnarray*} x \in \bigcap_{\alpha \in \emptyset} A_{\alpha} & \iff & x \in A_{\alpha} \text{ for all } \alpha \in \emptyset \\&\iff& \alpha \in \emptyset \to x \in A_{\alpha} \end{eqnarray*}$$

이 역시 집합 $\emptyset$ 이 원소를 가진다는 것은 공집합의 정의에 모순이므로, $\alpha \in \emptyset$ 은 거짓이다. [1] 공진리에 따라 $\alpha \in \emptyset \to x \in A_{\alpha}$ 은 참이고 그와 동치인 $\displaystyle x \in \bigcap_{\alpha \in \emptyset} A_{\alpha} $ 도 참이다.


  1. 이산수학 공부하다가 2018.07.13 22:06 댓글주소  수정/삭제  댓글쓰기

    이산수학 공부하다가 공진리 부분이 하도 이해가 안되서 며칠을 검색하다 이 글로 왔습니다.

    다름이 아니라 공진리 증명하실 때 제가 배운바에 따르면 x→y≡¬x∨y≡¬(¬(¬x∨y))≡¬(x∧¬y)를 이용한 것으로 보여지는데

    x→y≡¬x∨y를 증명할 때 진리표로 증명하는 것 밖에 안 배워서요.

    그럴경우 공진리를 전제로 하는 진리표이기에 순환 논증의 오류(?) 같은게 발생해서요.

    아마 다른 방법으로 증명하셨을텐데 그 방법이 무언가요?

    제 실력으로는 밑에 두가지가 쉽게 와닿지 않지만 첫번째는 쉽게 와닿아서요.

    바쁘시다면 첫번째에 관한 링크같은 것이라도 부탁드립니다 ㅠㅠ

    • BlogIcon 관리자 류ㄷH식 2018.07.14 11:36 신고 댓글주소  수정/삭제

      일단 $x \to y \equiv \lnot ( x \land \lnot y )$ 를 진리표로 증명하는 것 외에는 저도 들어본 적이 없습니다.

      그리고 교재에 따라 다른지 모르겠는데 제가 알기로 진리표는 공진리를 전제하지 않습니다.
      수학에서 진리표는 우리 인식과 맞도록 '정의'되고, 그 단계에서 '모순이란 무엇인가'하는 논의 자체가 필요 없습니다.

    • 답글 감사합니다 2018.07.14 13:05 댓글주소  수정/삭제

      먼저 바쁘실 텐데 답글 감사드립니다.
      제가 이산수학을 공부하던 중 교재에 있던 x→y의 진리표
      x y x→y
      T T T
      T F F
      F T T
      F F T
      에서 3, 4번째 줄에 있는 FTT, FFT 부분이 이해가 안가서 찾아보니 vacuous truth라고 해서 찾다찾다 이 글로 온거거든요.

      근데 책에서보니 저 진리표를 근거로 해서 x→y≡¬x∨y 증명했었는데
      포스팅하신 글에서 이를 이용해서 다시 공진리를 증명하는 부분이 이해가 안 갑니다.

      제가 교재를 처음에 봤을 때는 진리표가 FTT, FFT가 맞다는 전제 하에 써진 것으로 이해했었고,
      그래서 진리표를 통해 x→y≡¬x∨y를 증명하다보니 결국 앞선 저 전제하에 x→y≡¬x∨y를 증명하게 된 것이라고 생각했거든요.

      제가 본 Rosen북에서는 "If I am elected, then I will lower taxes."의 예를 들어서 설명하던데
      이런 식으로 일반적으로 받아들여지기에 공진리를 전제한 것이 아닌 것인지...
      그런데 막상 선출이 안되었다고 명제가 참이 된다는 보장도 없는 것 같고...
      결국 공진리를 전제한 것처럼 느껴지네요.
      그렇다면 방금 제가 이해한 부분에서 잘못된 부분이 있다는 것인데 시간이 나신다면 잘못된 부분을 짚어주시면 감사하겠습니다.

      영어랑 한국어랑 다 구글링해봤는데 대부분 제 이해수준을 훨씬 뛰어넘는 얘기거나
      아니면 그렇게 정한 거니 그냥 넘어가자는 식이 대부분이라서;;
      그래서 이글이 더 반가웠고 번거로우시겠지만 계속 어쭙게 되네요 ㅠㅠ;;

    • BlogIcon 관리자 류ㄷH식 2018.07.15 00:11 신고 댓글주소  수정/삭제

      설명에 앞서서 요약하자면, 제 대답은 '그렇게 정한거니 그냥 넘어가지는 식'입니다 ㅠㅠ;

      제가 보기에 집합론부터 시작하셨다면 and와 or부터 더 꼼꼼하게 공부하셨을텐데 그런게 생략되고 바로 $x \to y$ 가 나와버린 것 같습니다. 아마 공대생이신 것 같고, 그래서 이산수학부터 시작하시고 빨리빨리 진도를 빼다보니 이 사단이 난 것이 아닌가 합니다.

      말씀하신 교재에 따르면 공진리란 $x \to y$ 의 따름정리Corollary에 불과하며, 그것은 마치 $x \to y$ 가 공진리에서 확장되었다는 느낌을 준다는 것은 이해가 갑니다. 하지만, 미안하게도, 전혀 그렇지 않습니다.

      댓글에 쓰신 진리표에서 3, 4번째 줄이 공진리인것은 어찌보면 당연합니다. 그렇지 않고서야 $x \to y$ 를 이용해서 공진리를 증명할 수 있었을 리 없었으니까요. 하지만 그것이 공진리를 전제한다는 뜻은 아닙니다. 상대적으로 일반적인 정리는 상대적으로 특수한 정리를 함의하지만, 그것이 상대적으로 특수한 정리가 필요하다는 의미는 아닙니다. (세상의 그 어떤 증명이든 없던 사실을 만들 순 없습니다. 원래 사실이지만 눈에 띄지 않는 것을 눈에 보이도록 하는 게 '증명'입니다. 그리고 증명 없이도 눈에 보인다고 해서 순환논리가 되지는 않습니다.)

      질문자께선 공부의 순서가 거꾸로 되어서 무엇이 먼저고 무엇이 필요한지를 헷갈리신거라고 봅니다. 언급하신 진리표의 3,4번째 줄이 공진리를 의미한다고 했지 공진리가 있어야 그 진리표가 나온다고 한 적은 없었을 겁니다. 그 점을 잘 생각해보시면 궁금한 점이 풀릴겁니다.

    • 설명 감사합니다ㅠㅠ 2018.07.15 10:12 댓글주소  수정/삭제

      답변 정말로 감사드립니다 ㅠㅠ
      '세상의 그 어떤 증명이든 없던 사실을 만들 순 없습니다. 원래 사실이지만 눈에 띄지 않는 것을 눈에 보이도록 하는 게 '증명'입니다. 그리고 증명 없이도 눈에 보인다고 해서 순환논리가 되지는 않습니다.' 이 부분 덕분에 단번에 이해가 가네요.
      공부하면서도 어영부영 넘어가는 느낌이 드는 점이 많아서 집합론, 정수론부터 하고 싶었는데 시간내서 꼭 해야겠네요 ㅠㅠ
      별개로 양질의 글을 너무 많이 포스팅해주셔서 처음에 보자마자 바로 북마크 해놓았는데 앞으로도 공부하면서 자주 참고하겠습니다.
      좋은 포스팅과 멋진 답변 감사드립니다^^