by Corry Shores

[

**Search Blog Here**. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]

[The following is summary. My commentary is in brackets. Boldface is mine. I apologize in advance for any distracting typos or other errors.]

*Introduction to Logic*

There are a number of tautological equivalences that can be useful when making proofs about sets. Here is a list [note that Λ is the empty set and V is the domain of discourse]:

*A*and

*B*, the union of (or combined total of all members from)

*A*and

*B*is the same as of

*B*and

*A*, or:

(1)A∪B=B∪A

(Suppes 202)

*x*

(2)x∈A∪B↔x∈A∨x∈B(Suppes 203)

(3)x∈A∨x∈B↔x∈B∨x∈A(Suppes 203)

And corresponding to (2), we have:(4)x∈B∪A↔x∈B∨x∈A(Suppes 203)

*x*∈

*A*∪

*B*↔

*x*∈

*A*∨

*x*∈

*B*. It seems that we are saying with 2 that something is a member of the union of a first set with a second set if and only if it is a member of the first set or it is a member of the second set. Proposition 4 also follows this pattern. Perhaps that is what is meant by “corresponding”, but I am not sure] [In section 5.1 Suppes wrote, “for any

*x*and

*y*, if

*x*=

*y*, then

*y=x*. This fact is some times expressed by saying that the relation of identity is

*symmetric*. We notice also that if

*x=y*and

*y=z*, then

*x=z*. This fact is expressed by saying that the relation of identity is

*transitive*” (102).] Suppes then says we combine 2 through 4 from the transitivity and symmetry of equivalence, thereby concluding

(5)x∈A∪B↔x∈B∪A(203)

(2)x∈A∪B↔x∈A∨x∈B(3)x∈A∨x∈B↔x∈B∨x∈A(4)x∈B∪A↔x∈B∨x∈A

(4)x∈B∪A↔x∈B∨x∈A(4b)x∈B∨x∈A↔x∈B∪A

(3)x∈A∨x∈B↔x∈B∨x∈A(4b)x∈B∨x∈A↔x∈B∪A(*)x∈A∨x∈B ↔ x∈B∪A

(2)x∈A∪B↔x∈A∨x∈B(*)x∈A∨x∈B ↔ x∈B∪A(**)x∈A∪B↔x∈B∪A

(**)x∈A∪B↔x∈B∪A(5)x∈A∪B↔x∈B∪A

*principle of extensionality for sets*. It says that there is a principle of identity for sets when they have the same members:

*A*=

*B*↔(

*x*)(

*x*∈

*A*↔

*x*∈

*B*). So in our current case we have:

x∈A∪B↔x∈B∪A

*x*of the set

*A*∪

*B*are also the members of the set

*B*∪

*A*, this means that the two sets are identical.] Thus, Suppes explains, we can “conclude from 5 by the principle of extensionality for sets that

(6)A∪B=B∪A(Suppes 203)

*A*∪

*B*=

*B*∪

*A*could be:

x∈A∪B↔x∈A∨x∈B↔x∈B∨x∈A↔ x∈B∪A(Suppes 203)

one of the four characterizing equivalences:x∈A∪B↔x∈A∨x∈Bx∈A∩B↔x∈A&x∈Bx∈A~B↔x∈A&x∉Bx∈ ~A↔x∉A(Suppes 203)

A~ (A∩B) =A ~ B

*A*and

*B*.

*A*~(

*A*∩

*B*), and let us see if it marks the same region as

*A~B*. And let us start more specifically with

*A*∩

*B*.

*A*~(

*A*∩

*B*), in other words, what is in

*A*that is not in

*A*∩

*B.*

*A~B*, in other words, what is in

*A*that is not in

*B*. As we can see, it is in fact the same region.

A~ (A∩B) =A ~ B

x∈A~B↔x∈A&x∉B

*A*~ (

*A*∩

*B*). So we now have:

(1)x∈A~ (A∩B) ↔x∈A&x∉A∩B

*A*and

*B*:

x∈A∩B↔x∈A&x∈B

x∉A∩B

–(x∈A∩B)

x∈A∩B↔x∈A&x∈B

(1)x∈A~ (A∩B) ↔x∈A&x∉A∩B(2) ↔x∈A&–(x∈A&x∈B)

–(P & Q) ↔–P ∨–Q

(Suppes 34)(2) ↔x∈A&–(x∈A&x∈B)(3) ↔x∈A& (x∉A∨x∉B)

x★(y∘z) = (x★y) ∘ (x★ z).

(Suppes 131)(3) ↔x∈A& (x∉A∨x∉B)(4) ↔ (x∈A&x∉A) ∨ (x∈A&x∉B)

(P &–P) ∨ Q ↔ Q

(P &–P) ∨ Q ↔ Q(4) ↔ (x∈A&x∉A) ∨ (x∈A&x∉B)(5) ↔x∈A&x∉B

x∈A~B↔x∈A&x∉B(5) ↔x∈A&x∉B(6) ↔x∈A~B

A~ (A∩B) =A ~ Bx∈A~ (A∩B) ↔x∈A~B

*x*∈ ” component to it, but the original formulation does not. They are equivalent, but I do not know the rule that says so. I also do not know how we went from

*A*~ (

*A*∩

*B*) in the original formula to the

*x*∈

*A*~ (

*A*∩

*B*) in the first line of the proof. This is something he does in other cases too. Here is the whole proof.]

(1)x∈A~ (A∩B) ↔x∈A&x∉A∩B

(2) ↔x∈A&–(x∈A&x∈B)

(3) ↔x∈A& (x∉A∨x∉B)

(4) ↔ (x∈A&x∉A) ∨ (x∈A&x∉B) (5) ↔x∈A&x∉B

(6) ↔x∈A~BQ.E.D.

(Suppes 203)

*domain of discourse*or

*domain of individuals*(For example, in sociology, if we speak of the set of albinos, we implicitly mean only those albinos within the specific set of humans)] :

the first eight may be taken as axioms of a theory formalized in first order predicate logic with identity; with the addition of the axiom: (∃A)(∃B)(A≠B) and the appropriate definition of set difference the remaining twenty-three principles may be derived as theorems. Any model of these axioms is called aBoolean algebra, and the axioms are some times called the axioms for the algebra of sets.

(204)

(1)A∪ Λ =A

*identity element*with respect to the union operation” (205).

(2)A∩ V =A

THEOREM 1 (EXISTENCE OF RIGHT-HAND IDENTITY ELEMENT).

(∃y)(x)(x ∘ y = x)

(Suppes 105)

*A*is a subset of the domain V. Thus were they to intersect, you would have a set no different from

*A*.] “(2) says that the domain V of individuals is a right-hand

*identity element*with respect to intersection.

(3)A∪B=B∪A(4)A∩B=B∩A(Suppes 204)(3) and (4) are the commutative laws for union and intersection.

(Suppes 205)

(5)A∪ (B∩C) = (A∪B)∩ (A∪C)(6)A∩ (B∪C) = (A∩B)∪ (A∩C)

(Suppes 204)

Identities (5) and (6) are dualdistributivelaws. Notice that if we compare union to arithmetical addition and intersection to arithmetical multiplication, the analogue of (5) does not hold in arithmetic.

(Suppes 205)

(7)A∪ ~A= V

(Suppes 204)

Identity (7) is the set formulation of the law ofexcluded middle; everything in a given domain is either in a set or its complement. (Suppes 205)

(8)A∩ ~A= Λ

(Suppes 204)

In (8) we have the law ofcontradiction; nothing can be a member of both a set and its complement.

(Suppes 205)

(9)A∪A=A(10)A∩A=A(Suppes 204)Equations (9) and (10) express what is usually called theidempotencyof union and intersection. The problem of finding an arithmetical operation which is idempotent is left as an exercise.

(Suppes 205)

*idempotent*, in his

*A Dictionary of Philosophical Logic*, as:

IDEMPOTENT_{1 }A unary function or operation is idempotent if and only if applying that function twice to an argument produces the same result as applying it once. In other words, a unary function f is idempotent if and only if, for all x, we have:f(x) = f(f(x))IDEMPOTENT_{2 }A binary function or operation is idempotent if and only if, when we apply it to two instances of the same argument, we receive that same argument. In other words, a binary function f is idempotent if and only if, for all x, we have:x = f(x, x)In classical logic and most non-standard logics, the truth functions corresponding to conjunction and disjunction are idempotent.

(Cook 141)

(14) ~~A=A(15)A=~B → B= ~A(Suppes 204)Principle (14) is the law ofdouble negation, and (15) expresses a principle ofcontraposition.

(Suppes 205)

CONTRAPOSITIVE_{1 }Within categorical logic, the contrapositive of a categorical proposition is obtained by switching the subject term and predicate term of the proposition, and replacing the subject term and the predicate term with their complements.

(Cook 69)

(18)A∪ (B∪C) = (A∪B) ∪C(19)A∩ (B∩C) = (A∩B) ∩C(20)A∪ (A ∩B) =A(21)A ∩(A ∪B) =A(Suppes 204)In (18) and (19) we haveassociativelaws, which justify the omission of parentheses, and in (20) and (21) laws ofabsorption.

(Suppes 205)

(x) (y) (z) (x ∘ (y ∘ z) = (x ∘ y) ∘ z).

(Suppes 105)

ABSORBSION Given two binary functions f and g, absorbsion holds between f and g if and only if, for all a and b:f(a, g(a, b)) = g(a, f(a, b)) = aWithin Boolean algebra, absorbsion holds between the meet and join operators – that is:A ∩ (A ∪ B) = AA ∪ (A ∩ B) = AIn classical propositional logic, absorbsion holds between the truth functions associated with conjunction and disjunction – that is:A ∧ (A ∨ B) and: |A ∨ (A ∧ B) are logically equivalent to:A

(Cook 5-6)

(23) ~(A∪B) = ~A∩ ~B(24) ~(A∩B) = ~A∪B(Suppes 204)Equations (23) and (24) are De Morgan’s laws.

(Suppes 205)

–(P & Q) ↔–P ∨–Q–(P ∨ Q) ↔–P &–Q

(Suppes 34)

x∉ Λx∈ V

(13) Λ ≠ V

*x*∉ Λ and

*x*∈ V. Since he says that we need these assumptions for a proof, I presume that it is impossible to make the proof without them, but I am not sure how to show that.] [Recall again from section 9.2 the principle of extensionality for sets:

A=B↔ (x)(x∈A↔x∈B)

(Suppes 178)

Then by the principle of extensionalityx ∈ Λ ↔x∈ Vbutx∉ Λwhencex∉ V,which is absurd. Q.E.D.

(Suppes 205)

*x*∈ V.]

By considering an arbitrary member of a set and using tautological implications rather than tautological equivalences, useful principles of inclusion for sets are easily established. As an example we may consider:A∩B⊆A. |PROOF.(1)x∈A∩B↔x∈A&x∈ B(2) →x∈A. Q.E.D.Line (1) is an equivalence; the right-hand side of (1) tautologically implies the right-hand side of (2) but is not tautologically equivalent to it. The characterizing equivalence used for inclusion is, of course:A⊆B↔ (x) (x∈A→x∈B).

(Suppes 205-206)

In writing down proofs of inclusion relations between sets, one point needs to be remarked. Consider:(A∩B)~(B ∩ C) ⊆A.PROOF.(1)x∈ (A∩B)~(B ∩ C) ↔x∈A∩B&x∉B∩ C(2) →x∈A∩B(3) →x∈A&x∈B(4) →x∈AQ.E.D.The point is that although line (3) is tautologically equivalent to line (2), we use an implication sign in line (3), because this implication sign indicates the relation of (3) to the left side of (1), not to the right side of (2).

(Suppes 206)

*Introduction to Logic*. New York: Van Nostrand Reinhold / Litton Educational, 1957.

*A Dictionary of Philosophical Logic*. Edinburgh: Edinburgh University Press, 2009.

http://mrieppel.net/prog/truthtable.html

## No comments:

## Post a Comment