From: nguyen@drutx.ATT.COM (Christopher Chu)
Newsgroups: soc.culture.vietnamese
Subject: Re: [MISC] Logic puzzles solutions and respond to the self-claimed logicain, LONG NGUYEN
Summary: Solution to DDK's elementary set problem
Date: 29 Jul 92 01:55:17 GMT
Organization: AT&T Bell Laboratories - Denver, Colorado


 Dear SCV readers,

 I would like to contribute some of my understanding about logic in  this
 post by providing a solution to the elementary set problem stated by anh
 DDK, a Computer Science  Ph.D.  candidate  at  University  of  Edinburg,
 England,  as  a challenge to anh Long Nguyen, a netter who has seemed to
 possess high interest in logic (?) and who has  already  self-designated
 as a logician on the net.

 I realize that the given problem is a  classical  grade-school  exercise
 since,  like DDK and possibly many other people who have been acquainted
 with set theory, I learned this problem right after being introduced  to
 first-order-predicate  calculus  in  a  vietnamese  high  school at 11th
 grade. Also, since no other netter has volunteered to post the solution,
 I would like to take this opportunity to do so. I would appreciate it if
 interested netters would give me comments on my rather clumsy statements
 below.

 ----------------------------------------------------------------------
 Problem: prove that any empty set is a subset of a non-empty set.
 ----------------------------------------------------------------------

 In mathematics, a "set" is a collection of distinct objects;  an  "empty
 set"  is  *the*  set that contains no object; and a "non-empty set" is a
 set that is not the empty set.

 In set theory, to prove that the set A is a subset of set B, we need  to
 show that each and every member of set A is a member of set B.

 The statement that is to be proven can be restated as follows.

 (a) For all x, if x is a member of the empty set, then x is a member  of
     a non-empty set.

 By  mathematical  logic,  the  above  statement  is  equivalent  to  the
 following:

 (b) For all x, either x is not a member of the  empty  set  or  x  is  a
     member of a non-empty set.

 Since (b) is obviously true by definition  of  the  empty  set  and  the
 property of disjunction (e.g., the logical "or" operation), the original
 problem statement "an empty set is a subset of a non-empty set" is  also
 true.
                                                                    QED
 ----------------------------------------------------------------------

 The equivalence between (a) and (b) that I have just stated is one among
 the fundamentals of mathematical logic. By definition, validity of those
 two statements  are  determined  based  on  the  following  truth  table
 (assuming readers have some knowledge about logic).

 +---+---+--------+--------+
 | A | B | A -> B | ~A v B |   A is True or False, exclusively
 +---+---+--------+--------+   B is True or False, exclusively
 | F | F |   T    |    T   |
 | F | T |   T    |    T   |   ~A     reads "not A"
 | T | F |   F    |    F   |   A->B   reads "if A then B"
 | T | T |   T    |    T   |   A v B  reads "A or B"
 +---+---+--------+--------+

 Basically, the realization that the the empty set is  a  subset  of  any
 non-empty ones in set theory is partially analogous to the understanding
 that adding 0 and a non-zero integer N produces N  in  elementary-school
 arithmetic.  What  more  in  solving  the  empty  set  exercise  is  the
 understanding as why logic should be the way it is.  This  understanding
 is  just one among the very beginning steps of any kind of logic in this
 world.

 I  sincerely  believe  that  most  undergraduate  students   who   study
 philosophy and who have some training in techniques of formal reasoning,
 engineering students who have some introduction to boolean algebra in  a
 logic  design  course and students who major in mathematics have already
 grasped the basic concepts of the mathematical logic that underlies  the
 elementary set problem given by anh DDK.

 I also realize that a formal understanding of more serious topic such as
 NP-completeness  in  the  complexity  theory  (intuitively,  this  study
 investigates whether there exist problems  that  cannot  be  universally
 solved  by any polynomial time/space algorithms and vice versa) requires
 advanced understanding of much higher level of logic that ought to cover
 most theories of computation and related formal language studies in this
 century. I want to indicate that the information in this article is very
 elementary  to  people who have advanced knowledge about logic and by no
 means represents a test to anyone.

 Sincerely Yours,

 Chris Chu, nguyen@drutx.ATT.COM (Internet), att!drutx!nguyen (UUCP)