Philosophical Devices Week 1 – Introduction to Naïve Set Theory



Download 43.79 Kb.
Date03.05.2016
Size43.79 Kb.
Philosophical Devices

Week 1 – Introduction to Naïve Set Theory

---------------------------------------------------------------------------------------------------------



Definitions & Such

  • Set=df any well-defined collection of ‘objects’

  • Element=df the objects in a set

  • Membership=df the relation elements bear to the sets they are in


Notation. Typically, sets are denoted with upper-case letters, elements with lower-case letters – e.g. ‘A, B, C…’ for sets, ‘a, b, c…’ for elements. Membership is standardly expressed using ‘’.


  • x  A – the element x is a member of set A

  • x  A – the element x is not a member of set A

  • A - x – the set A has as a member the element x

  • A - x – the set A doesn’t have as a member the element x


Extensive specification: name all the members of a particular set

  • {1, 2, 3}, {Schnieder, Schramme, Recki, Puster, Gahde}, {Socrates, {Socrates}}


Intensive specification: specify the ‘feature’ all the members share

  • {x| x is a integer 1 x  3}, {x: x is a professor}, {x| (x=Socrates) or (x={Socrates}) }


Axiom of Extensionality: two sets are identical iff they have all and only the same elements

  • For all sets A & B: A=B iff (x)( x  A iff x  B)

Two special sets:

- The Empty set; the set that has nothing as a member

 - The Universal set; the set that has everything as a member


Is there more than one empty set? How about more than one Universal set?

---------------------------------------------------------------------------------------------------------



Further Relations & Operations

Union: The union of two sets is the set which contains everything that belongs to either or both. Similar to logical ‘or’ operator.
Intersection: the intersection of two sets is the set which contains everything that belongs to both. Similar to logical ‘and’ operator.
Notation: we express union using ‘’, and intersection using ‘’

  • {Socrates, Plato}  {Cicero} = {Socrates, Plato, Cicero}

  • {Socrates, Plato}  {Plato}= Plato

  • {Socrates}  {Plato} = 


Subset: B is a subset of A iff all the members of B are members of A.

Proper Subset: B is a proper subset of A iff all the member of B are members of A and BA
Notation: we express subset using ‘’, and proper subset using ‘’

  • {Socrates}  {Socrates, Plato}

  • {Socrates}  {Socrates, Plato}

  • {Socrates}  {Socrates}

  •   {Schnieder, Schramme, Recki, Puster, Gahde}

  • Socrates  {Socrates}

{Gähde, Schnieder, {Schramme, Recki}}



  • Schnieder: a member, not a subset

  • {Schramme, Recki}: a member& a subset

  • { Gähde }: not member, is a subset

  • Recki: neither member nor subset


Power Set: the set of all a set’s subsets; the power set of a set with n-members has 2n members

  • {Socrates, Plato} = {{Socrates, Plato}, {Socrates}, {Plato}, }

  • {} = {}

  • {Hesperus, Phosphorus} =


Difference: The difference of two sets consists of the elements of the first set that do not belong to the second set. Thus, for two sets A & B, the difference of A and B is the set consisting of those elements of A that are not in B, standardly written as ‘A B’ (note: A B is sometimes also called the relative complement of B relative to A)
A B =def {x| x A and x B}
Let A = {Socrates, Schnieder, Schramme} & B = {Schnieder, Cicero, Schramme}

  • A B =

  • A – {Socrates} =

  • {Socrates} – A =

Complement: the compliment of a set A, written A’, is the set consisting of everything not in A


A’=df {x| x ∉ A}

  • Using A from the previous example, A’=

  • {{Socrates} – A}’ =

---------------------------------------------------------------------------------------------------------
An aside on Ordering, Cartesian Products, Relations & Functions
Ordered pair: written ‘<a,b>’, where a is considered the first element and b is the second element of the pair. Importantly, <a,b> < b,a >, unlike with standard sets!

Definition: <a,b> =df {{a}, {a,b}}
Cartesian product: the Cartesian product of A and B, written ‘AB’, is the set consisting of all ordered pairs which take an element of A as the first member of the pair and an element of B as the second.

Definition: AB=df { | x ∈ A and y ∈ B}


We can extend the above story for all ordered n-tuples, where n is any natural number. For example, ordered triples are usually defined as: <a,b,c> =df <<a,b>,c>. And for three sets A, B and C the Cartesian product can be defined as: ABC =df ((A  B)  C)
Using these tools, it is possible to formalize talk about relations – e.g. ‘part of’, ‘sister of’, ‘in same room as’, etc.
Similarly for functions – A relation F from A to B is a function from A to B iff:

(i) Each element in the domain of F is paired with just one element in the range, i.e., <a,b>F and <a,c>F iff b=c

(ii) The domain of F is equal to A

---------------------------------------------------------------------------------------------------------



Russell Ruins Everything – The Axiom of Comprehension

Comprehension: For any condition , there exists a set A such that for all x, xA iff x

Take the set of all sets with just one member. Does it have itself as a member?

How about the set of all set with more than one member?
Let  = is not self-membered. Is there a set for this condition?
Suppose there is – call it R (for Russell). We can now ask, is RR or RR?
Let RR. By definition, R contains all and only those sets that are not members of themselves. This means that, if RR, then RR. So, RR. But, this is contradicts our initial assumption that RR. Therefore, it is not the case that RR.
Alternatively, let RR. By definition, R contains all and only those sets that are not members of themselves. This means that, if RR, then RR. So, by assumption, RR. But, this contradicts our initial assumption that RR. Therefore it is not the case that RR.
Problem: if it is not the case that RR, then RR, and if it is not the case that RR, then RR. Yet, given the reasoning above, we know that neither RR nor RR.
The only solution is to go back and find an assumption we relied upon to reject.

---------------------------------------------------------------------------------------------------------



Exercises

(Note: these are identical to the exercises included at the end of Chapter 1)


1. What is the union of the following pairs of sets?

(a) {Abe, Bertha}, {Bertha, Carl}

(b) {2, 5, 7, 11, 13}, {1, 5, 11, 13}

(c) {x: x is a child aged 7-12}, {x: x is a child aged 10-15}

(d) {France, Germany, Italy}, {Germany, Italy}

(e) {France, Germany, Italy}, {India, China}

(f) {x: lives in Germany}, {x: x lives in Europe}

(g) {x: x lives in China}, {x: lives in Europe}

(h) {x: x weighs more than 10 kilos}, {x: x weighs more than 7 kilos}
2. What is the intersection of each of the above pairs of sets?
3. List all the subsets of the following sets.

(a) {Abe, Bertha}

(b) {7, 8, 9}
4. Give the power sets of the following sets.

(a) {1, 7}

(b) {London, Manchester, Birmingham}
5. Consider the set {1, 2, 3, 7, 8}

Which of the following items are (a) members (b) subsets or (c) neither?


2, {7,8}, {2,3}, {}, 3, {1, 2, 3, {7,8}}
6. Consider the set {1, 2, 3, {7,8}, {2,3}}

Which of the following items are (a) members (b) subsets or (c) neither?


2, {7,8}, {2,3}, {}, 3, {1, 2, 3, {7,8}}
7. (A): ‘This sentence is false.’ Show carefully that the supposition that (A) has a truth value leads to a contradiction.


Share with your friends:




The database is protected by copyright ©essaydocs.org 2020
send message

    Main page