Set Theory and ZFC - The Subset Principal - Searcoid, Page 7

[Math Amateur]

I am reading Micheal Searcoid's book: Elements of Abstract Nalysis ( Springer Undergraduate Mathematics Series) ...

I am currently focussed on Searcoid's treatment of ZFC in Chapter 1: Sets ...

I am struggling to attain a full understanding of the Subset Principle which reads as shown below ... see NOTE 1 ... indeed I cannot, with any confidence, construct examples of this principle using various sets $$x$$ and various functional conditions $$\phi$$ ...


Can someone please help by illustrating the working of the principle by providing several examples ... ?

Help will be much appreciated ...

Peter==================================================*** NOTE 1 ***

Searcoid's statement of the Subset Principle and its proof reads as follows:View attachment 5039==========================================================*** NOTE 2 ***

Now, I will be providing some text from Searcoid to give MHB readers a sense of Searcoid's approach and his notation ... but members who have a good understanding of ZFC will only have to skim the text provided ... (apologies for the length of the text, but I think it may help members understand the post ... )In the above text, Axiom III is mentioned, so I am providing the Axiom plus some of Searcoid's remarks on it ...https://www.physicsforums.com/attachments/5040
View attachment 5041Again, to give MHB members a sense of Searcoid's approach and notation, I am providing some of Searcoid's introductory remarks on ZFC ... View attachment 5042
View attachment 5043

 

[Math Amateur]

I am reading Micheal Searcoid's book: Elements of Abstract Nalysis ( Springer Undergraduate Mathematics Series) ...

I am currently focussed on Searcoid's treatment of ZFC in Chapter 1: Sets ...

I am struggling to attain a full understanding of the Subset Principle which reads as shown below ... see NOTE 1 ... indeed I cannot, with any confidence, construct examples of this principle using various sets $$x$$ and various functional conditions $$\phi$$ ...


Can someone please help by illustrating the working of the principle by providing several examples ... ?

Help will be much appreciated ...

Peter==================================================*** NOTE 1 ***

Searcoid's statement of the Subset Principle and its proof reads as follows:==========================================================*** NOTE 2 ***

Now, I will be providing some text from Searcoid to give MHB readers a sense of Searcoid's approach and his notation ... but members who have a good understanding of ZFC will only have to skim the text provided ... (apologies for the length of the text, but I think it may help members understand the post ... )In the above text, Axiom III is mentioned, so I am providing the Axiom plus some of Searcoid's remarks on it ...
Again, to give MHB members a sense of Searcoid's approach and notation, I am providing some of Searcoid's introductory remarks on ZFC ...

Just a followup question to my own post ... how does specifying a set using a logical condition avoid Russel's paradox?

Hope someone can clarify this point ...

Pet

 

[Deveno]

One of the classic examples (we are essentially talking about *set-builder notation*, here) is:

$a = \Bbb Z$

$\phi(z) = 2|z$ ($2$ divides $z$)

in which case $\psi(x,z)$ defines the set $b = 2\Bbb Z$

In other words, the subset of the integers which consists of exactly the even integers is a well-defined, and unique, subset.

Sets are *exacting* in this regard, unlike, say *concepts*, where the collection of "brown-haired guys" is not so precisely defined (part of this has to do with the way we assume intuitively "everything-that-exists" isn't any different, conceptually, than "any one thing that exists", something which is NOT true of sets-to define a subset this (the way your post describes) way, the superset is require a priori).

In a finite mathematical universe, we could do away with such niceties-sets could be enumerated explicitly, every time. However, as soon as we have infinite sets (such as the natural numbers, the canonical example), this is no longer possible. Instead, we wish to specify sets by criteria they satisfy. For example, the set $2\Bbb Z$ above can also be seen as the *image* of the function:

$f \subset \Bbb N \times \Bbb N$ which pairs $(k,k+k)$ (the "doubling function").

I urge you to consider how one would ensure the set of all even integers could be rigorously defined without such a principle.

Set-theorists are usually *very* precise about the "qualifications" in their definitions-the idea being, that properly constructed logical statements about sets could be verified *automatically* by, say, a computer program, or an equivalent abstraction, such as a Turing machine. As a consequence of this, the formal statements of ZF set theory are often hard to paraphrase in "natural language".

Without going into some rather intense detail, there is a 3-tier system of logics in modern mathematics:

Propositional logic, which uses only simple connectives (this is something of an over-simplification, but it will have to do, for now).

First-order logic, which quantifies over variables, but not over predicates or propositions.

Second-order logic, which quantifies over variables and predicates or propositions.

Each higher logic is capable of expressing things that just can't be said in the lower forms. By analogy, we are talking about the difference between these 3 kinds of statements:

Peter is mortal.
All men are mortal.
Everything that can be said to be true for all men, is also true of mortal men.

*****************

At first, it was thought that all that was necessary to determine a set, was to list the properties it must have, so:

$y = \{x|\phi(x)\}$

would be a set.

There were, historically, two objections raised to this:

1. If $\phi(x) =$ "$x$ is a set", we would have a never-ending hierarchy of the set of all sets:

$S = \{S\{S\{S\dots\}\}\}$

Such a set is said to be "ill-founded", and the modern theory has axioms which prevent this. Note that there *do* exist mathematical objects which have this kind of behavior, like infinite sequences which can have "tails" that are the entire sequence, for example:

$0,1,0,1,0,1,\dots...$

(pairing each sequence *entry* with a natural number as its "domain" avoids this "eating one's own tail" behavior)

2. If $\phi(x) = x\not\in x$, then we get "Russel's set", which leads to logical contradiction.

Now, note the difference if we say:

$y = \{x \in z| x\not\in x\}$. Here $z$ is some set established before-hand.

Now, we aren't testing $x$ "universally", but only testing elements of the well-defined set $z$ for property $\phi(x) = x\not\in x$.

One of the consequences of the above is that we need to "build-up" sets from "known" sets to have a "large enough vocabulary" of sets to restrict. Typically, one must then allow the existence of at least one set, often the empty set is given this privilege. One can then construct "bigger" sets using pairing, unions, power sets and the axiom of infinity.

 

[Math Amateur]

One of the classic examples (we are essentially talking about *set-builder notation*, here) is:

$a = \Bbb Z$

$\phi(z) = 2|z$ ($2$ divides $z$)

in which case $\psi(x,z)$ defines the set $b = 2\Bbb Z$

In other words, the subset of the integers which consists of exactly the even integers is a well-defined, and unique, subset.

Sets are *exacting* in this regard, unlike, say *concepts*, where the collection of "brown-haired guys" is not so precisely defined (part of this has to do with the way we assume intuitively "everything-that-exists" isn't any different, conceptually, than "any one thing that exists", something which is NOT true of sets-to define a subset this (the way your post describes) way, the superset is require a priori).

In a finite mathematical universe, we could do away with such niceties-sets could be enumerated explicitly, every time. However, as soon as we have infinite sets (such as the natural numbers, the canonical example), this is no longer possible. Instead, we wish to specify sets by criteria they satisfy. For example, the set $2\Bbb Z$ above can also be seen as the *image* of the function:

$f \subset \Bbb N \times \Bbb N$ which pairs $(k,k+k)$ (the "doubling function").

I urge you to consider how one would ensure the set of all even integers could be rigorously defined without such a principle.

Set-theorists are usually *very* precise about the "qualifications" in their definitions-the idea being, that properly constructed logical statements about sets could be verified *automatically* by, say, a computer program, or an equivalent abstraction, such as a Turing machine. As a consequence of this, the formal statements of ZF set theory are often hard to paraphrase in "natural language".

Without going into some rather intense detail, there is a 3-tier system of logics in modern mathematics:

Propositional logic, which uses only simple connectives (this is something of an over-simplification, but it will have to do, for now).

First-order logic, which quantifies over variables, but not over predicates or propositions.

Second-order logic, which quantifies over variables and predicates or propositions.

Each higher logic is capable of expressing things that just can't be said in the lower forms. By analogy, we are talking about the difference between these 3 kinds of statements:

Peter is mortal.
All men are mortal.
Everything that can be said to be true for all men, is also true of mortal men.

*****************

At first, it was thought that all that was necessary to determine a set, was to list the properties it must have, so:

$y = \{x|\phi(x)\}$

would be a set.

There were, historically, two objections raised to this:

1. If $\phi(x) =$ "$x$ is a set", we would have a never-ending hierarchy of the set of all sets:

$S = \{S\{S\{S\dots\}\}\}$

Such a set is said to be "ill-founded", and the modern theory has axioms which prevent this. Note that there *do* exist mathematical objects which have this kind of behavior, like infinite sequences which can have "tails" that are the entire sequence, for example:

$0,1,0,1,0,1,\dots...$

(pairing each sequence *entry* with a natural number as its "domain" avoids this "eating one's own tail" behavior)

2. If $\phi(x) = x\not\in x$, then we get "Russel's set", which leads to logical contradiction.

Now, note the difference if we say:

$y = \{x \in z| x\not\in x\}$. Here $z$ is some set established before-hand.

Now, we aren't testing $x$ "universally", but only testing elements of the well-defined set $z$ for property $\phi(x) = x\not\in x$.

One of the consequences of the above is that we need to "build-up" sets from "known" sets to have a "large enough vocabulary" of sets to restrict. Typically, one must then allow the existence of at least one set, often the empty set is given this privilege. One can then construct "bigger" sets using pairing, unions, power sets and the axiom of infinity.

Hi Deveno ... thanks for the help ...

Just reflecting on your post ...

A first thought is that the "set" $$a$$ is acting like what elementary set theory presentations in various books call the "universe of discourse" (which Searcoid does not mention) ... ... and then from this universe, we use a property $$\phi$$ to determine what elements of the universe of discourse constitute the set $$b$$ defined by the property $$\phi$$ ... is my interpretation correct? partially correct? flawed? ... ...

Seems like Searcoid is avoiding the universe of discourse idea and trying to act in a universe where all objects are sets ... not sure how he is dealing with "elements" of a set ... except that sets can be elements of other sets ... but ... seems to make understanding what he is saying a little difficult ..

A further question is ... why do we need the logical condition $$\psi$$ with two variables ... it seems that $$b$$ is clearly and uniquely defined with declaration of the universe of discourse $a = \Bbb Z$ and the definition of $$\phi$$ as follows:

$\phi(z) = 2|z$ ($2$ divides $z$)

then $$b = \{ z \ | \ \phi(z) \}$$ ... ...

so then ... why do we need $$\psi$$ ... what role or purpose is it fulfilling ... ..

Can you comment on the above and clarify matters?

Peter

 

[Evgeny.Makarov]

One is allowed to consider objects that satisfy some formula $\phi(x)$, but one is not always allowed to call the collection of such objects a "set". One situation when it is allowed is when we consider only elements of a collection that has already been designated a "set".

A first thought is that the "set" $$a$$ is acting like what elementary set theory presentations in various books call the "universe of discourse" (which Searcoid does not mention) ... ... and then from this universe, we use a property $$\phi$$ to determine what elements of the universe of discourse constitute the set $$b$$ defined by the property $$\phi$$ ... is my interpretation correct?

Yes, your interpretation is quite correct. One remark is that in elementary set theory the universe of discourse is often fixed for the whole problem. (E.g., consider a group of students. Some of them speak English, some Spanish, some both and so on. The remainder of the problem talks only about this group of students.) Here one is allowed to form subsets of arbitrary sets and can freely change the universe of discourse every time the construction (that is, Theorem 1.1.2, which uses Axiom III) is applied.

A further question is ... why do we need the logical condition $$\psi$$ with two variables ... it seems that $$b$$ is clearly and uniquely defined with declaration of the universe of discourse $a = \Bbb Z$ and the definition of $$\phi$$

The construction of a new set using a property $\phi$ uses Axiom III, which involves $\psi$. That is, given a set $a$ and a property $\phi$, you provide Axiom III with $a$ and a formula $x=z\land \phi(z)$, and this axiom returns you the set $\{x\in a\mid \phi(x)\}$.

 

[Math Amateur]

One is allowed to consider objects that satisfy some formula $\phi(x)$, but one is not always allowed to call the collection of such objects a "set". One situation when it is allowed is when we consider only elements of a collection that has already been designated a "set".

Yes, your interpretation is quite correct. One remark is that in elementary set theory the universe of discourse is often fixed for the whole problem. (E.g., consider a group of students. Some of them speak English, some Spanish, some both and so on. The remainder of the problem talks only about this group of students.) Here one is allowed to form subsets of arbitrary sets and can freely change the universe of discourse every time the construction (that is, Theorem 1.1.2, which uses Axiom III) is applied.

The construction of a new set using a property $\phi$ uses Axiom III, which involves $\psi$. That is, given a set $a$ and a property $\phi$, you provide Axiom III with $a$ and a formula $x=z\land \phi(z)$, and this axiom returns you the set $\{x\in a\mid \phi(x)\}$.

Thanks Evgeny ... a really helpful post ... still reflecting on what you have said ... but, your post took me forward quite a way in understanding ZFC ... thank you!

Peter