by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[Central Entry Directory]
[Logic & Semantics, Entry Directory]
[The following is summary. All boldface, underlying and bracketed commentary are my own, unless noted otherwise.]
Gary Hardegree
“Basic Set Theory”
(A course text for his class “Philosophy 595 - Formal Semantics”)
§§1-8
Brief Summary:
Set Theory describes the structures and logical properties of groupings. A set may be made of ‘ur-elements’ and/or of other sets. But two sets cannot have the same members, because in fact they would be identical and would never have been separate sets to begin with. We may define a set using a ‘set-abstraction’ method, meaning that we describe the members not by actually listing each of them between curly brackets but rather by defining the conditions for the set’s membership, by means of a formulation like {v : ℱ}. What this means is that the set (between the curly brackets) includes those members v that fulfill formula ℱ. For example, the set of happy things would be formulated as: {x : x is happy}. More specifically the formulation would read:
{v : ℱ} =df ℩S∀v(v ∈ S ↔ ℱ)
which means, the set of v things fulfilling formula ℱ is defined as that specific (℩) set S which contains all the items v that fulfill ℱ. [Or: the set made of those things v which fulfill formula ℱ is defined as being that one specific set S such that for all v, v is a member of S if and only if it fulfills that formulation ℱ.] However, set theory does not normally use the description operator ℩ seen above. Instead it is ‘hidden’ in a ‘set-abstract conversion’:
∀v(v ∈ {v : ℱ} ↔ ℱ) [set=abstract conversion]
Here, v is any variable, and ℱ is any formula. The following is a simple example.
∀x(x ∈ {x : x is happy} ↔ x is happy)
This says that something is an element of {x : x is happy} if and only if it is happy.
(page 6, quotation)
[This set-abstraction is reminiscent of the Tarski (T) scheme, which reads:
(T) X is true if, and only if, p.
For example,
“Snow is white” is true if, and only if, snow is white.
Here truth is defined as satisfaction, meaning that some sentence is true only if what it says is true. Similarly, the set-abstraction seems to be defining set membership in terms of satisfaction, namely, that something is a member of a set if it satisfies the conditions for membership in that set.]
Summary
1. Introduction
Formal semantics makes use of set theory. We will look at ideas in set theory “that have bearing on formal semantics” (2).
2. Membership
“sets have members, also called elements” (2). Epsilon ‘∈’
symbolizes membership. [It takes the Greek letter equivalent to ‘e’, for ‘elements.] If we want to say that element a is a member of set S, we write:
a ∈ S
If we want to say it is not a member, then we write:
a ∉ S
Conventionally we use lower case Roman-Italic letters to denote ‘points’ (elements or members), and we use Roman-Italic capital letters for sets whose elements are points. Some sets contain other sets as members. For them we use script letters or some other “gaudy font” (2). So in the following, we have an element included in a set, and that set is included in a set which contains other sets.
a ∈ B & B ∈ ℂ
[Hardegree then seems to suggest that we need not follow that convention necessarily.]
Note, however, that the following is equally legitimate.
a ∈ b & b ∈ c
(2)
3. Extensionality
“Sets have members, just like clubs.” Yet, consider how “two different clubs can have the same membership” and thus “a club is not identified with its membership, nor even by its membership” (2). However, this cannot be so in set theory: “two different sets cannot have the same membership” (2). [So, if two sets are said to have the same members, then they are identical, and thus there is only that one set with two names.] This restriction is called the Principle of Extensionality.
The Principle of Extensionality:
for any set A, and for any set B:
∀x(x ∈ A ↔ x ∈ B) → A = B [extensionality](Hardegree, p.3, bracketing his)
[The basic insight of the above formulation is that one set of members can have different names, but that set can only ever be one set. For, two different sets may not have the same membership. Informally it says that if set A and set B have the same members, then they are the same set. Less informally it say: for any set A and for any set B, for all members x, if all such x’s are included in A if and only if they are included in B, then A equals B.]
4. The Empty Set
All sets have members, with one exception, the empty set.
Empty set:
there is a set S such that ∼∃[x ∈ S] [empty set]
(Hardegree, p.3, bracketing his)
As the principle of extensionality says that there may be only one set for any unique group of members, this means there can only be one empty set. “It is fittingly called the empty set, and is denoted ∅.” (4)
5. Simple Sets; Singletons, Doubletons, etc.
Normally when we denote a set with only a few elements, we merely list those elements within curly brackets and separate the items with commas. Here are some of Hardegree’s examples. (3)
{Mozart}
{Mozart, Jupiter}
{Mozart, Jupiter, 41}
Hardegree then gives the following informal definitions for this structure.
{a} =df the set whose only element is a
{a,b} =df the set whose only elements are a and b
{a,b,c} =df the set whose only elements are a, b, and c(page 3)
Then Hardegree provides the following principles to formally summarize these above definitions. [The basic insight of these formulations is that something is included within a set if it is a member of that set. Informally they read something like, for all x, x is included in the set whose members are a, b, and c, if and only if x is either a, b, or c.]
∀x ( x ∈ {a} ↔ x=a )
∀x ( x ∈ {a,b} ↔ x=a ∨ x=b )
∀x ( x ∈ {a,b,c} ↔ x=a ∨ x=b ∨ x=c )(page 3)
Next Hardegree provides the following terminology:
{a} is called the singleton (unit set) of a.
{a,b} is called the doubleton (unordered-pair) of a and b.
{a,b,c} is called the tripleton (unordered triple) of a, b, and c.
etc.(page 3)
If a, b, and c are all well-defined, then sets {a}, {a,b}, {a,b,c} will as well be well-defined. [Now, for some reason, probably having to do with what is meant by well-defined] “set theory postulates the existence of infinitely-many sets, including the following, just for starters.
∅, {∅}, {{∅}}, {{{∅}}}, etc.
(page 3)
[which perhaps means, the null set, the set containing the null set as a member, the set containing the set containing the null-set as a member, and so on]
Hardegree says it is important that we “appreciate how many sets are alluded to by the above list”, so he will demonstrate two things, that, 1) “the above list has infinitely-many entries,” and 2) “the above list contains no duplicates!” (page 4). [The proof is excluded in our summary but can be read on page 4.]
6. Pure and Impure Sets
A set which contains only other sets is called pure. However, a set can be
constructed from an underlying universe of ‘ur-elements’, which are presumed not to be sets, as in the following (from earlier).
{Mozart, Jupiter, 41}
(page 5)
Such sets made of non-sets are called impure.
7. Set Abstraction
Many sets have more than three members, and so it is impractical to use the listing convention we employed above. Instead,
a more concise notation is employed – set-abstraction, whose basic form is
{v : ℱ}
where v is a variable, and ℱ is a formula.
(page 5)
[It seems it is saying that ℱ is a formula containing the free variable v, and that formulation may for example predicate that variable.]
The following are simple examples.
{x : x is happy}
{x : x is happy and x is virtuous}
{x : the mother of x is taller than x}(page 5)
[It seams that the first set in the list is the set of (all) happy things. Perhaps it could be read, ‘the set containing members x such that x are happy’, or maybe something like ‘the set containing members x where x are happy’.]
The intuitive idea is quite simple – {v : ℱ} consists of exactly those things that satisfy the condition described by the formula ℱ. For example, {x : x is happy} consists of exactly those things that satisfy the condition of being-happy.
(page 5)
[To understand the following formulation, let us consider some things. {v : ℱ} is a set of things which satisfy the formulation of ℱ, for example, ‘is happy’. We will use the definite-description-operator, ‘℩’, which seems to be a way to refer to one specific thing. In this case, it seems we give the set {v : ℱ} the name S. And it seems we define {v : ℱ} as being the one particular S in question. And this S has only those members that fulfill the formula ℱ. So in the following,
℩S
seems to mean, the (one and only, specific) set S ….
And,
∀v(v ∈ S ↔ ℱ)
would mean, for all v, v is a member of set S if and only if it fulfills the formulation ℱ.
So together,
{v : ℱ} =df ℩S∀v(v ∈ S ↔ ℱ)
seems to mean, the set made of those things v which fulfill formula ℱ is defined as being that one specific set S such that for all v, v is a member of S if and only if it fulfills that formulation ℱ. However, I am not sure if this is correct. Does the ℱ standing alone in the biconditional mean “v fulfills ℱ”? (Some text below seems to indicate this.) Also, I cannot explain the next bracketed text, reading “[S not free in ℱ]”. Does this mean ‘where S is not free in ℱ”? How could that be, if S is not a variable? How can the set S be ‘in’ the formula ℱ which conditions S’s members? Please read Hardegree’s text yourself to find a better interpretation.]
The following is the official explicit definition.
{v : ℱ} =df ℩S∀v(v ∈ S ↔ ℱ)
[S not free in ℱ] [set-abstract]Here, the symbol ‘℩’ (upside-down iota) is the definite-description-operator, informally defined as
follows.
℩vℱ =df the v such that ℱ(Hardegree, p.5, bracketing his)
8. Set-Abstract Conversion
So above we saw the official definition for set-abstraction, which again is (in part):
{v : ℱ} =df ℩S∀v(v ∈ S ↔ ℱ)
And as we noted, it uses the description-operator, ℩.
However, the description-operator is almost never employed in set theory. Rather, it usually gets hidden under an associated principle of set-abstract conversion.
(6)
[The following formulation seems to be saying, for all variables v, v is a member of set {v : ℱ} (the set whose members fulfill formula ℱ) if and only if v fulfills formula ℱ. Then the example might be read as, for all x, x is included in the set of all happy things if and only if x is happy.]
∀v(v ∈ {v : ℱ} ↔ ℱ) [set=abstract conversion]
Here, v is any variable, and ℱ is any formula. The following is a simple example.
∀x(x ∈ {x : x is happy} ↔ x is happy)
This says that something is an element of {x : x is happy} if and only if it is happy.
(Hardegree, p., bracketing his)
[Note: I changed to Hardegree’s double-struck F symbol :
to script capital F, ℱ , because it was not showing in the published version of this blog post.]
Hardegree, Gary. “Basic Set Theory”. A course text for his class “Philosophy 595 - Formal Semantics”.
http://people.umass.edu/gmhwww/595/text.htm
http://people.umass.edu/gmhwww/595/pdf/set%20theory/Set-Theory-Chap0.pdf
No comments:
Post a Comment