Articles

0.3: Basic set theory


0.3: Basic set theory

MATH Basic set theory

part 1: find an x in A that is not B and prove this x in A is not in B
(1) x=p
(a) x=p is in A since p can be defined by A
(b) Hence, x=peA
(2) Assume x is in B
(a) Then, x can be defined by B
(3) Solve for n and substitute p for x
(a) Because the value of n produced when x=p is not in the set of possible values for B (part 0), x=p is not in B
(4) Hence, there is an x in A that is not in B and therefore, A is not a subset of B

part 1: ACB
(1) Let xeA be arbitrary
(a) Then x=f(a)
(2) Can x=f(a) be defined such that x=f(a)=f(b)? Let f(ab)
(a) Use f(a)=f(b) that isolates a in terms of b and substitute a in terms of b (ab) into the definition of A, f(a) such that f(ab)
(b) Solve and rearrange f(ab) such that f(ab) looks like f(b), isolating any variable if necessary
(c) If a variable was isolated, name the variable using f(a)=f(b) and replace ab with that variable to clearly show that f(ab)=f(b)
(d) Hence, xeB and upside-down-Ax, xeA implies xeB

part 2: BCA
(1) Let xeB be arbitrary
(a) Then x=f(b)
(2) Can x=f(b) be defined such that x=f(b)=f(a)? Let f(ba)
(a) Use the definition f(b)=f(a) and substitute b in terms of a into f(b) such that f(ba)
(b) Solve and rearrange f(ba) such that f(ba) looks like f(a), using any variable if need be to make it clear that f(ba)=f(a)
(c) If a variable is used, be sure to define it using our f(b)=f(a) relationship
(d) Hence, xeA and upside-down-Ax, xeB implies xeA

U(k=i, k=n)Ak=AiUAi+1UAi+2. An where U(k=i, k=n) equals the largest subset

xeX: xeAk for some nonnegative integer k in the parameters

U(k=i, infinity)Ak=Ak where U(k=i, infinity) where U(k=i, infinity) equals the largest, subset

U(k=i, k=n)Ak=AinAi+1nAi+2n. nAn where U(k=i, k=n)Ak equals the "most included" subset, sometimes the zero set

xeX: xeAk for all nonnegative integers k in the parameters k=i, k=n

Given three sets A, B, and C, the cartesian product is <(a,b,c):aeA and beB>for all a, b, and c in A, B, C


1. On the Origins

Let us first discuss a few basic concepts of set theory. A set is a well-defined collection of objects. The items in such a collection are called the elements or members of the set. The symbol “” is used to indicate membership in a set. Thus, if is a set, we write to say that “ is an element of ,” or “ is in ,” or “ is a member of .” We also write to say that is not in . In mathematics, a set is usually a collection of mathematical objects, for example, numbers, functions, or other sets.

Sometimes a set is identified by enclosing a list of its elements by curly brackets for example, a set of natural numbers can be identified by the notation

.

More typically, one forms a set by enclosing a particular expression within curly brackets, where the expression identifies the elements of the set. To illustrate this method of identifying a set, we can form a set B of even natural numbers, using the above set , as follows:

.

which can be read as “the set of such that is even.” Of course,

is even.

It is difficult to identify the genesis of the set concept. Yet, the idea of a finite collection of objects has existed for as long as the concept of counting. Indeed, mathematicians have been investigating finite sets and methods for measuring the size of finite sets since the beginning of mathematics. For example, the above two sets

are finite sets. As every element in is an element in , the set is said to be a subset of , denoted by . Since there are elements in that are not in , we say that is a proper subset of . Moreover, the number of elements in is strictly smaller than the number of elements in . Thus, one can say, “the whole is greater in size than its proper part .”

Infinite sets lead to an apparent contradiction. Consider the infinite sets:

.

We view the sets and as existing entities that both contain infinitely many elements. Thus, and are “completed infinities.” Observe that every element in is in , and that is a proper subset of . However, if, as many mathematicians once believed, “infinity cannot be greater than infinity,” then the whole is not greater in size than its proper part . This counterintuitive result was viewed by many early prominent mathematicians as being contradictory, as it appeared to conflict with the well-understood behavior of finite sets. These mathematicians thus concluded that the concept of a “completed infinity” should not be allowed in mathematics.

For this reason, before Cantor, a majority of mathematicians considered infinite collections to be mathematically illicit objects. Cantor was the first mathematician to view infinite sets as being legitimate mathematical objects that can coexist with finite sets. Clearly, the size of a finite set can be measured simply by counting the number of elements in the set. Cantor was the first to investigate the following question:

Can the concept of “size” be extended to infinite sets?

Cantor addressed this question in the affirmative by using the concept of a function to measure and compare the sizes of infinite sets. Functions are widely used in science and mathematics. For sets and , we say that is a function from to , denoted by : , if and only if is a relation (operation) that assigns to each element in , a single element in . There are three important properties that a function might possess:

  • : is an injection if and only if for each in there is at most onein such that .
  • : is a surjection if and only if for each in there is at least onein such that .
  • : is a bijection if and only if for each in there is exactly onein such that .

Observe that : is an injection if and only if distinct elements in are assigned to distinct elements in that is, for all and in , if , then . Also note that : is a bijection if and only if : is an injection and a surjection.

Cantor observed that two sets and have the same size if and only if there is a one-to-one correspondence between and , that is, there is a way of evenly matching the elements in with the elements in . In other words, Cantor noted that the sets and have the same size if and only if there is a bijection : . In this case, Cantor said that and have the same cardinality. For an illustration, let be the set of natural numbers and let be the set of even natural numbers. Now let : be defined by . One can verify that : is a bijection and, thus, we obtain the following one-to-one correspondence between the set of natural numbers and the set of even natural numbers:

Hence, each natural number corresponds to the even number , and each even natural number is thereby matched with . The bijection : specifies a one-to-one match-up between the elements in and the elements in . Cantor concluded that the sets N and E have the same cardinality.

Cantor also defined what it means for a set to be smaller, in size, than a set . Specifically, he said that has smaller cardinality (smaller size) than if and only if there is an injection : but there is no bijection : . Cantor then proved that there is no one-to-one correspondence between the set of real numbers and the set of natural numbers. Cantor’s proof showed that the set of real numbers has larger cardinality than the set of natural numbers (Cantor 1874). This stunning result is the basis upon which set theory became a branch of mathematics.

The natural numbers are the whole numbers that are typically used for counting. The real numbers are those numbers that appear on the number line. For example, the natural number , the integer , the fraction , and all of the other rational numbers are real numbers. The irrational numbers, such as and , are also real numbers. Again, let be the set of natural numbers, and let be the set of real numbers. If a set is either finite or has the same cardinality as the set of natural numbers, then Cantor said that it is countable. Since the set of real numbers is larger, in size, than the set of natural numbers , Cantor referred to the set as being uncountable.

After proving that the set of real numbers is uncountable, Cantor was able to prove that there is an increasing sequence of larger and larger infinite sets. In other words, Cantor showed that there are “infinitely many different infinites,” a result with clear philosophical and mathematical significance.

After his introduction of uncountable sets, in 1878, Cantor announced his Continuum Hypothesis (CH), which states that every infinite set of real numbers is either the same size as the set of natural numbers or the same size as the entire set of real numbers. There is no intermediate size. Cantor struggled, without success, for most of his career to resolve the Continuum Hypothesis. The problem persisted and became one of the most important unsolved problems of the twentieth century. After Cantor’s death, most set theorists came to believe that the Continuum Hypothesis is unresolvable.

Cantor’s profound results on the theory of infinite sets were counterintuitive to many of his contemporaries. Moreover, Cantor’s set theory violated the prevailing dogma that the notion of a “completed infinity” should not be allowed in mathematics. Thus, the outcry of opposition persisted. Influential mathematicians continued to argue that Cantor’s work was subversive to the true nature of mathematics. These mathematicians believed that infinite sets were dangerous fictional creations of Cantor’s imagination and that Cantor’s fictions needed to be eradicated from mathematics (Dauben 1979, page 1) (Dunham 1990, pp. 278-280). Nevertheless, Cantor’s theory of sets soon became a crucial tool used in the discovery and establishment of new mathematical results, for example, in measure theory and the theory of functions (Kanamori 2012). Mathematicians slowly began to see the utility of set theory to traditional mathematics. Accordingly, attitudes started to change and Cantor’s ideas began to gain acceptance in the mathematical community (Dauben 1979, pp. 247-248). The significance of Cantor’s mathematical research was eventually recognized. David Hilbert, a prominent twentieth century mathematician, described Cantor’s work as being

the finest product of mathematical genius and one of the supreme achievements of purely intellectual human activity. (Hilbert 1923)

Ultimately, Cantor’s theory of abstract sets would dramatically change the course of mathematics.


Table of Contents

The main notions of set theory (cardinals, ordinals, transfinite induction) are fundamental to all mathematicians, not only to those who specialize in mathematical logic or set-theoretic topology. Basic set theory is generally given a brief overview in courses on analysis, algebra, or topology, even though it is sufficiently important, interesting, and simple to merit its own dedicated treatment.

This book provides just that in the form of a leisurely exposition for a diversified audience. It is suitable for a broad range of readers, from undergraduate students to professional mathematicians who want to finally find out what transfinite induction is and why it is always replaced by Zorn's Lemma.

The text introduces all main subjects of &ldquonaive&rdquo (nonaxiomatic) set theory: functions, cardinalities, ordered and well-ordered sets, transfinite induction and its applications, ordinals, and operations on ordinals. Included are discussions and proofs of the Cantor&ndashBernstein Theorem, Cantor's diagonal method, Zorn's Lemma, Zermelo's Theorem, and Hamel bases. With over 150 problems, the book is a complete and accessible introduction to the subject.

Advanced undergraduates, graduate students, and research mathematicians.

Lovely little book &hellip does a truly marvelous job in covering what every one in the game should know, whether he be an analyst, geometer, algebraist or number theorist&mdashor anything else, for that matter. It's all there, from Cantor's theory of cardinals to transfinite induction, from Zermelo to Zorn &hellip it is a terrific book and does everything right: its selection of topics is not only logical, it is elegant, and the coverage is superb &hellip The problems are very nice: interesting and non-trivial &hellip and they supplement the main body of the text very well &hellip the book is a pedagogical marvel &hellip would be perfect for self-study &hellip would also be a marvelous experience &hellip to use the book in a first course on set theory &hellip a very nice bit of work &hellip I very recently used the book's proof of the existence of a Hamel basis for any vector space in my course on Advanced Linear Algebra. It is an extremely slick and quick argument &hellip And the discussion given in the book is typical of the entire book: to the point, elegant, and complete &hellip I highly recommend this book &hellip it covers the basic set-theoretic tool-kit every mathematician should carry around at all times, and does so with style. And then there are all the beautiful applications, challenging and elegant problems, and even a lot of surprises.

Well-written with excellent exercises both elementary and advanced &hellip It would serve nicely either as a text or as independent reading.


Basic set theory

Access-restricted-item true Addeddate 2014-08-06 19:00:14.133756 Bookplateleaf 0002 Boxid IA1146307 City Berlin, Heidelberg [usw.] Donor bostonpubliclibrary External-identifier urn:oclc:record:851370139 Extramarc UCLA Voyager Foldoutcount 0 Identifier basicsettheory00levy_0 Identifier-ark ark:/13960/t9575dk35 Invoice 1213 Isbn 0387084177
9780387084176 Lccn 78001913 Ocr ABBYY FineReader 11.0 Openlibrary OL4715584M Openlibrary_edition OL4715584M Openlibrary_work OL5956845W Page-progression lr Pages 418 Ppi 300 Related-external-id urn:isbn:1306362253
urn:oclc:868966265
urn:isbn:3662023105
urn:isbn:3540084177
urn:lccn:78001913
urn:oclc:439033328
urn:oclc:637186553
urn:oclc:721982589
urn:oclc:781139627
urn:oclc:797219573
urn:oclc:251769601
urn:oclc:3669426
urn:isbn:3662023083
urn:oclc:864077468
urn:isbn:0486420795
urn:lccn:2002022292
urn:oclc:441241117
urn:oclc:488910564
urn:oclc:49225700
urn:oclc:494835212
urn:oclc:777682359
urn:oclc:807938892
urn:oclc:845493844
urn:oclc:849206222
urn:oclc:861054407 Republisher_date 20161221114432 Republisher_operator [email protected] Republisher_time 561 Scandate 20161219144542 Scanner ttscribe19.hongkong.archive.org Scanningcenter hongkong Shipping_container SZ0023 Worldcat (source edition) 251769601

4. Comparing Foundation and Anti-Foundation

The purpose of this section is to compare FA and AFA in a technical way, using ideas from category theory. That is, the language of category theory and especially its built-in feature of duality are used to say something insightful about the relation between FA and AFA. Further, the dual statements about the axioms suggest a much more systematic and thoroughgoing duality about a host of other concepts. This deeper point is not a strictly mathematical result but rather more of a research program, and so the final subsection here will detail some of what is known about it.

As we said, our work here begins to use category theory. We realize that not all readers will be familiar with that subject at all. So we shall try to make this section as accessible as possible. In particular, we&rsquoll only present those notions from category theory that we actually need in our work of this section. We also illustrate all of the definitions on a few categories which will be of interest. And as we go on in future sections, we&rsquoll develop only the background that we need. [11]

Our use of category theory is mainly for the terminology and intuition. We know that there are philosophical issues connected with the use of category theory as a foundation for mathematics. This entry does not deal with any of these issues in a head-on way.

Initial and final objects.

We need a definition from category theory. Fix a category C. An object x is initial if for every object y there is exactly one morphism f&thinsp:&thinspx &rarr y Dually, an object x is final if for every object y there is exactly one morphism f&thinsp:&thinspy &rarr x.

In Set , the empty set is an initial object for every set y, the empty function is the only function from &empty to y. In addition, the empty set is the only initial object.

As for final objects, every singleton <x> is a final object. For every set y, the constant function with value x is the only function from y to x. And the singletons are the only final objects in the category.

4.1 The category of sets, the category of classes

We refer the reader to the entry on category theory for the definitions of category and functor.

We need to mention the objects and morphisms in the categories of sets and of classes, and also to spell out the functors of interest on them.

Set . The objects are the sets, and the morphisms are triples &langx, y, f&rang, where f&thinsp:&thinspx &rarr y. That is, each triple &lang x, y, f&rang is a morphism from x to y. The identity morphism ida for a set a is &langa, a, f&rang , where f is the identity function on a and the composition operation of morphisms is given by:

Functors on Set . The polynomial operators on sets extend to endofunctors on Set . The way that these operations are defined on morphisms is straightforward and may be found in any book on category theory. Here is a brief summary: For any set s, the constant functor with value s is a functor on Set . It takes every function to ids. For any two functors F and G, we have a functor F× G defined by (F× G)(a) = Fa × Ga here we use the cartesian product on sets. If f&thinsp:&thinspa &rarr b, then

We also have a functor F+G defined by (F + G)(a) = Fa+ Ga using the coproduct on sets, that is, the disjoint union. Here the action on morphisms is by cases

A special case is Fx = x + 1. That is, Fx is the disjoint union of x with a singleton. And if f&thinsp:&thinspx &rarr y, then Ff&thinsp:&thinspFx &rarr Fy works in much the same way, taking the new point in x to the new point in y, and otherwise behaving like f.

The power polynomial operators also extend to endofunctors on Set : on morphisms f&thinsp:&thinspx &rarr y, the function &weierpf: &weierpx &rarr &weierpy takes each subset a &sube x to its image

The morphisms are then triples consisting of two formulas with parameters defining the domain and codomain, and a third one with two free parameters defining the action of the morphism.

Functors on Class . The functors of interest are again the power polynomials. They are defined on Class similarly to the way they are defined on Set . For our purposes, the main difference between the two categories is that in Set we cannot solve &weierp(x) = x, while we can do so in Class .

4.2 Algebras for a functor

Here is a basic example that illustrates why these are called algebras. Let&rsquos take the category Set of sets, and the functor

For the object N of natural numbers, HN is thus two copies of N×N. We&rsquoll use colors to indicate the different copies, with red for the first copy and blue for the second. So we can view HN as

One example of an algebra for this functor is (N, &alpha), where &alpha( a, b ) = a + b and &alpha( a, b ) = a × b. In other words, &alpha operates on the red pairs by adding and on the blue pairs by multiplying.

Getting back to the terminology of &ldquoalgebra&rdquo, the point is that the function &alpha does the work of the two tables. The function &ldquois&rdquo the tables.

Here is another example of an algebra. This time we are concerned on Set with Fx = x +1, as defined above. The algebra we have in mind is (N, s). Here s&thinsp:&thinspN+1 &rarr N takes the natural number n to its successor n+1, and the new point in N+1 to the number 0.

Up until now, we have merely given examples of algebras for different functors. The advantage of the categorical formulation is that the usual notions of a morphism of algebras turn out to be special case of a more general definition.

Let (c, f) and (d, g) be algebras for the same functor F on the category C. A morphism of algebras from (c, f) to (d, g) is a morphism &alpha&thinsp:&thinspc &rarr d so that the diagram below commutes:

(This means that the two compositions, &alpha &sdot f and g&sdotF&alpha, are the same function.)

It now is clear that we have a category of algebras for a given functor. And so we immediately have the concept of initial and final algebras. There is no guarantee that these exist, but in many interesting cases they do. The reason we are interested in initial algebras is their connection to recursion.

To see this in detail, we return to the functor Fx = x + 1 on Set . We saw the algebra (N, s) above. We claim that this is an initial algebra. What this means is that for any algebra (A, a), there is a unique algebra morphism h&thinsp:&thinsp (N, s) &rarr (N, s). That is, the diagram below commutes:

Thue function a from A+1 to A may be decomposed into a map i&thinsp:&thinspA &rarr A together with an element b &isin a. And to say that the diagram above commutes is the same thing as saying that h(0) = b, and for all n &isin N, h(s(n)) = a(h(n)).

Stepping back, the purported initiality of (N, s) is the same as the following assertion:

This is the standard form of the Principle of Recursion on N. The upshot is that this principle is equivalent to the assertion that (N, s) is an initial algebra of the functor Fx = x +1.

One way to interpret this equivalence is that we can take the existence of an initial algebra for Fx = x+ 1 as an axiom of set theory, in place of the usual Axiom of Infinity. That axiom says that there is an algebra for the singleton functor Sx = <x> on sets which contains &empty as an element and whose structure is the inclusion. This principle is easier to state than the algebraic reformulation. It takes a bit of work to use the simpler standard formulation to derive the Recursion Principle, and this is one of the basic topics in any course on axiomatic set theory.

Two general facts: First, the structure map of an initial algebra on Set is always a bijection. This follows from a very general result in category theory due to J. Lambek. And from this we see that &weierp has no initial algebras on Set , by Cantor&rsquos Theorem.

Initial algebras for polynomial functors on Set .

Let F&thinsp:&thinsp Set &rarr Set be a power polynomial functor. We know that F is monotone (it preserves the subset relation on sets), and it is not hard to check a slightly stronger property: F preserves inclusion maps between classes: An inclusion is a map ia, b&thinsp:&thinspa &rarr b on classes which &ldquodoesn&rsquot do anything&rdquo: a must be a subset of b, and for all x &isin a, i(x) = x. We say that F is standard if it preserves inclusions in the sense that Fia, b = iFa, Fb. Once again, every power polynomial endofunctor on Set is standard.

The polynomial operations on sets (without power) are also continuous: they preserve countable unions of sets.

Let F&thinsp:&thinsp Set &rarr Set be a polynomial endofunctor. We sketch the proof that the least fixed point F* carries the structure of an initial algebra, together with the identity on it.

One forms the increasing sequence

We write 0 for &empty. Each of the maps shown is an inclusion, by standardness. Let F* be the union of the increasing sequence F n 0 of sets. Then F(F*) = F* by continuity. So (F*, id) is an algebra for F. To check initiality, let (A, a) be an algebra for F, so a&thinsp:&thinspFa &rarr a. Define maps gn&thinsp:&thinspF n (0) &rarr A by recursion, with g0&thinsp:&thinsp0 &rarr A the empty function (this is what initiality of &empty amounts to), and gn+1 = a &sdot Fgn. Check that we have an increasing sequence of functions

then take the union to get &phi &thinsp:&thinsp F* &rarr A. One checks that this &phi is a morphism of F-algebras, and indeed is the only such.

4.3 Coalgebras for a functor

We now turn to coalgebras. Again, let F be an endofunctor on a category C. A coalgebra for F is a pair (c, f), where c is an object of C, and f&thinsp:&thinspc &rarr Fc. Comparing this to the definition of an algebra, we can see that a coalgebra is the same kind of structure, except that the direction of the arrow is reversed.

For example, every graph is a coalgebra of &weierp on F&thinsp:&thinsp Set &rarr Set . That is, every graph (G,&rarr) may be re-packaged as (G, e), with e&thinsp:&thinspG &rarr &weierp G given by e(x) = <y &isin G : x&rarr y>. In words, we trade in the edge relation of a graph with the function that assigns to each point its set of children. This re-packaging has an inverse, and so the notions of &ldquograph as set with relation&rdquo and &ldquograph as coalgebra of &weierp&rdquo are in this sense notational variants. [12]

Let (c, f) and (e, g) be coalgebras for the same functor. A morphism of coalgebras from (c, f) to (d, g) is a morphism &alpha&thinsp:&thinspc &rarr d in the category C so that the diagram below commutes:

A coalgebra (d, g) is a final (or terminal) coalgebra if for every coalgebra (c, f), there is a unique morphism of coalgebras &alpha&thinsp:&thinsp(c,f) &rarr (d,g).

Here is another example as we wind our way back to set theory. These are based on discussions at the beginning of this entry, concerning streams of numbers (Section 1.1). We are dealing with the functor Fa = N×a. Then a system of stream equations is a coalgebra for F. To see how this works in a concrete case, we return to equation (2), reiterated below:

We regard this system as a coalgebra (X, e), where X = <x, y, z>, e(x) = &lang0,y&rang , and similarly for e(y) and z(x) . So now we have a concrete example of a coalgebra for this F. Another coalgebra for F uses the set N &infin of streams as its carrier set. The coalgebra itself is

This coalgebra is final. We shall not verify this here, but instead we apply this point. By finality, there is a unique e &dagger &thinsp:&thinspX &rarr N &infin such that the diagram below commutes:

We now follow the elements of X around the diagram both ways. For x, this tells us that

That is, e &dagger (x) is a stream whose first component is 0 and whose second component is e &dagger (y). Similar observations hold for e &dagger (y) and e &dagger (z), of course. The upshot is that the three streams e &dagger (x), e &dagger (y) and e &dagger (z) are exactly the ones we are after.

Much the same applies to the tree example from Section 1.2.

4.4 The axioms again

At this point we rephrase FA and AFA to make a comparison. Recall that V is the class of all sets, and that V = &weierpV. This means that (trivially) the identity on the universe maps V onto &weierpV, and vice-versa. Despite this, we want to introduce notation for these two maps that makes them different. We shall write

Thus i takes a multiplicity (a set of sets) and regards it as a unity (a set). We also have a map in the other direction

This j takes a set and regards it as a set of sets.

The Foundation Axiom in Algebraic Form. Except for not being a set, (V, i) is an initial algebra for &weierp: for all sets a and all f&thinsp:&thinsp&weierp a &rarr a, there is a unique s&thinsp:&thinspV &rarr f such that m = f &sdot &weierp m:

The Anti-Foundation Axiom in Coalgebraic Form. Except for not being a set, (V, j) is a final coalgebra for &weierp: for every set b and every e: b&rarr &weierpb, there exists a unique s&thinsp:&thinspb &rarr V such that s = &weierp s &sdot e:

The map s is called the solution to the system e.

Class forms. We only mentioned forms of the axioms pertaining to sets. They are a little nicer when stated as axioms on Class :

FA is equivalent to the assertion that (V, i) is an initial algebra for &weierp on Class .

AFA is equivalent to the assertion that (V, j) is a final coalgebra for &weierp on Class .

4.5 Conceptual comparison

A chart just below indicates a kind of conceptual comparison of iterative and coiterative ideas. The entries towards the top are dualities in the categorical sense. Moving downwards, the rows in the chart are more like research directions than actual results. So spelling out the details in the chart is more like an ongoing research project than a settled matter.

For many functors on Set , especially polynomial functors and the finite power set functor, the initial algebra is the least fixed point together with the identity. For the polynomial functors, this least fixed point is itself an algebra of terms.

algebra for a functor coalgebra for a functor
initial algebra final coalgebra
least fixed point greatest fixed point
congruence relation bisimulation equivalence relation
equational logic modal logic
recursion: map out of an initial algebra corecursion: map into a final coalgebra
Foundation Axiom Anti-Foundation Axiom
iterative conception coiterative conception
set with operations set with transitions and observations
useful in syntax useful in semantics
bottom-up top-down

The connection between greatest fixed points and final coalgebras is the content of the following result.

The original result used much weaker hypotheses on F, using notions which we did not define, so our statement is rather weaker than in Aczel&rsquos book. Several papers have gone on to weaken strengthen this Final Coalgebra Theorem.

Bisimulation. We have given the definition of bisimulation earlier, in Section 3.1. We discussed it in connection with graphs, but the reader may also know of a notion with the same name coming from modal logic. Actually, the theory of coalgebra studies a more general notion, that of bisimulation on a coalgebra for a given functor, defined first in Aczel and Mendler (1989). This more general notion specializes to several concepts which had been proposed in their own fields. In addition, it is (nearly) the dual concept of a congruence on an algebra this explains our line in the conceptual comparison chart.

Equational logic and modal logic. A great deal of work has shown ways in which equational logic and modal logic are &ldquodual&rdquo, but to spell this out in detail would require quite a bit more category theory than we need in the rest of this entry.

There is a growing field of coalgebraic generalizations of modal logic. For a survey of this area, see Kurz (2006).

The final coalgebra of a functor may be regarded as a space of complete observations. (As with all our points in this section, this statement is mainly for functors on Set , and the notion of &ldquocomplete observation&rdquo is, of course, merely suggestive.) For example, let AtProp be a set whose elements are called atomic propositions, and consider the functor F(a) = &weierpfin(a) × &weierp(AtProp ). A coalgebra for this is a set a together with one map of a into its finite subsets, and another map into the collection of sets of atomic propositions. Putting the two maps together gives a finitely-branching Kripke model: each point has finitely many children and some set of atomic propositions. Now modal logic gives us a way of &ldquoobserving&rdquo properties of points in coalgebras (Kripke models). And the record of everything that one could observe from a point is the modal theory of that point. Further, one may take the collection of all theories of all points in all finitely-branching Kripke models and make this collection (it is a set) into the carrier of a final coalgebra for the functor. Indeed, this would be one way to construct a final coalgebra.

Corecursion. Returning now to the chart, we present an example of a corecursive definition. The equation for zip given above shows how the zip function on streams is to work. It should satisfy

Here is how zip is uniquely defined via a corecursive definition. Write N &infin × N &infin as S in this discussion. We want a map from S to N &infin . We are dealing with S as the final coalgebra of the functor Fa = N × a. And we&rsquoll write the structure on the final coalgebra as &lang&thinsp head , tail &thinsp&rang, just as we did it in Section 1.1. The idea is to turn S into the carrier set of a coalgebra for, say (S, f). Then zip will be the unique coalgebra morphism from (S, f) to (S, &lang&thinsp head , tail &thinsp&rang ). It remains to define f. Let

As mentioned, by finality there is a unique zip &thinsp:&thinspS &rarr N &infin so that the diagram below commutes:

To make sure that this works, we follow an arbitrary pair of streams, say &langs,t&rang around the square, starting in the upper-left. Going down, we have the stream zip (s, t). From this, the structure takes this to &lang head ( zip (s, t)), tail ( zip (s, t))&rang &isin FN &infin . But we could also take our &langs, t&rang across the top via f to get &lang head (s), &langt, tail (s)&rang&rang. Now F zip applies to this pair, and this is where the action of F as a functor enters. We get &lang head (s), zip ( tail (t), s)&rang. So overall, we have

just as desired. It says: to zip two streams, start with the head of the first, and then repeat this very process on the second followed by the tail of the first.

The main point of this demonstration is that the principle of finality is sufficient to define and study corecursive definitions. There are many further developments in this area.

Sets, again. We have already discussed at length the lines in the table concerning the Foundation and Anti-Foundation Axioms, and their attendant conceptual backgrounds. The point of this section is to situate that entire discussion inside of a larger one.

Examples of final coalgebras and corecursive definitions. Our conceptual comparison makes the point that algebras embody sets with operations. This point is almost too easy: the reason behind the terminology of &ldquoalgebras&rdquo in category theory is that sets with operations may be modeled as algebras in the categorical sense. For coalgebras, it is harder to make the case that they directly correspond to sets with either &ldquotransitions&rdquo or &ldquoobservations&rdquo. However, we present a few examples that motivate this point.

Functor Fa coalgebra final coalgebra logic
S × a stream system infinite streams over S a : &phi for a &isin S
(S × a) + 1 stream system, allowing ends finite and infinite streams over S add an &ldquoend of stream marker&rdquo
&weierpa graph = Kripke frame = system of set equations pointed graphs modulo bisimulation a fragment of infinitary modal, no atoms
&weierpfina × &weierp(AtProp) finitely branching Kripke model over the set AtProp of atomic propositions a certain subset of the canonical model a fragment of modal logic over AtProp

The table above lists a few functors on Set or Class along with final coalgebras or other data from the conceptual comparison chart.

First, for any set S, the functor Fa = S× a. A coalgebra for this F is a stream system of equations as we saw it in Section 1.1, except that there we made things concrete and took S to be the set of natural numbers. The final coalgebra is the set S &infin = S × S &infin of streams over S. The logical language for this functor would be a sentential (propositional) language whose sentences are either true or of the form s : &phi where s&isinS. The semantics would be the obvious one for example

One should note that carrier of the final coalgebra may be taken to be certain theories in this language. These may be described extrinsically as the theories of all points in all coalgebra. It is more informative, however, to set down a logical system and then consider the maximal consistent sets in the system. With the right definition, the maximal consistent sets do turn out to be the carrier of a final coalgebra for the functor.

Second, we consider Fa = (S × a) + 1. Here 1 = <0>and + is the disjoint union operation. However, it is more common for people to represent the one and only element of 1 using a symbol like *. The coalgebras are like stream systems of equations, except now an equation might ask for a stream to &ldquostop&rdquo by having * on the right-hand side. So an example of a coalgebra would be x &asymp &langs,y&rang , y &asymp *. Then the solution would take x &dagger to be the one-term sequence s. The logic for this functor would be the same logic (HML) as before, except that now we add an atomic sentence to detect the ends of finite sequences.

Turning to the last two lines, we already know that AFA is equivalent to the assertion that (V, id) is a final coalgebra of &weierp also, even without AFA, we have a final coalgebra whose carrier set is the pointed graphs modulo bisimulation. The logic in this case is infinitary modal logic, actually, it is a fragment of this logic. It turns out that two points in a given coalgebra have the same infinitary modal theory iff they are bisimilar.

The line concerning &weierpfin(a) × &weierp(AtProp) is the closest to the Kripke semantics of modal logic. One might hope that the final coalgebra would turn out to be the canonical model of the modal logic K, but this is not quite right. One needs to cut down to those maximal consistent sets which are realized by some point in some finitely branching model.

As the reader may notice, we are being extremely vague about matters concerning the logics: is there a principled explanation of where they come from? What, if anything, is the relation between the final coalgebras and canonical models as we find them in modal logic? The explanations here are too long and too involved for this entry. Once again, one place to start reading about these matters is Kurz (2006).

The lines in at the bottom of the conceptual comparison chart are the most programmatic of all.

Doing without AFA: final coalgebras in ZF. We mentioned in note [2] that it is possible to alter the pairing operation in such a way that one may prove many of the results that our treatment obtains only by using ZFA. This points is mentioned in Forster (1994) and developed in detail in Paulson (1999) (and in other papers by Paulson). One replaces the Kuratowski pair &langx,y&rang with a variant, (<0>× a)&cup (<1>× b). (This is the usual disjoint union operation, also called the coproduct on sets.) Then one defines variants of other notions: the cartesian product, functions, etc. And in terms of these one can indeed study streams and infinite trees, and many other sets of interest in this entry. Even more, one can prove final coalgebra theorems, stating sufficient conditions for the existence of a final coalgebra whose structure is the identity. (This is an important point for this line of work: in ZF we can show the existence of final coalgebras for the same functors as in ZFA, but in the latter theory we can get final coalgebras whose structure maps are the identity.)

One might think that this move undermines much of the interest in AFA. For Paulson, the reduction is important since he wants to use an automatic theorem prover to work with assertions in set theory. It makes sense to work out detailed reductions so as to avoid changing the set theory.

Otthers may not find this conclusive, for two reasons. First, the method doesn&rsquot apply to equations like x = <x>, or to collections like x = &weierpfin(x). The latter kind of equation is especially useful in applications. But even more, what will be of interest will be the whole assembly of what we might call coalgebraic concepts: coinduction, corecursion, and top-down treatments of various phenomena. Someone who is using these concepts and is also worried about modeling in set theory would probably find it convenient to work with AFA, even if many of the end applications could be done in standard set theory.

To put things differently, and to ask a question that surely belongs in this entry, why should one work with AFA instead of FA? Much depends on the purposes one brings to set theoretic modeling in the first place. For most purposes, including most of mathematics, it makes little or no difference. To model some circular phenomena, it turns out to be convenient to work with final coalgebras of various functors. It is especially nice with the structure maps on those final coalgebras may be taken to be the identity function. For example, this would allow us to say that a stream of numbers really and truly is an ordered pair of a number and a stream. In this case, having AFA would be nice, but the results above show that in many of the interesting cases, it is not actually needed. On the other hand, if one is content to work with isomorphisms, then having the structure map be the identity is a kind of &ldquooptional extra&rdquo. Further, the question of which axiom to adopt might appear to be besides the point.

Interested readers may consult the following supplementary document for a discussion of how the more general ideas from coalgebra and closely related fields help with discussions of the kinds of mathematical circularity which we looked at previously.


Solutions: Sets and Set Theory

There are four suits in a standard deck of playing cards: hearts, diamonds, clubs and spades.

C is the set of whole numbers less than 10 and greater than or equal to 0. Set D is the even whole numbers less than 10, and set E is the odd whole numbers less than 10.

Set G is the set of all oceans on earth. Set E is a set of some rivers, and set F is a list of continents.

Set Z is the set of all types of matter. Set X is a set of some metals and set Y is a set of some gases.

Set A lists the element r twice. So the objects in this set are not unique.

Basic Notation

Liquid is an element of set R .

The number 7 is an element of set G .

The colors red, white and blue are all colors of the US flag, and are all elements of set B .

A bobcat was not listed in set X .

All of these territories are outside of the United States.

Types of Sets

Set G has a finite number of elements.

Set H is the set of integers, which has an infinite number of elements.

Each set listed in Exercise 3 is a finite set.

The integers is the only set in Exercise 4 that is infinite.

There are no cars with 20 doors, so this set is empty (null).

Set Equality

Since P and Y contain exactly the same number of elements, and the elements in both are the same, we say that P = Y.

Set Q contains the element 7, which is not an element of set H . Thus HQ

M = <0, 2, 4, 6, 8, 10>and N = <0, 2, 4, 6, 8>. Therefore MN.

Since X and Y contain exactly the same number of elements, and the elements in both are the same, we say that X = Y.

Since A and B are both empty sets, we say that A = B.

Venn Diagrams

A = <2, 4, 6, 8>and the range given for A is non-inclusive.

Choice 1 uses the wrong notation, choice 2 is correct, choice 3 is wrong, and choice 4 is wrong.

This Venn diagram represents the intersection of P and Q, which is 6.

The elements 2, 3, 5, 7, and 11 are all elements of X .

The union of X and Y is shown in this Venn diagram, by the shaded region.

Subsets

Sets X, Y, and Z are each subsets of set G.

Every element of the set of vowels is contained in the set of the alphabet .

Since 9 is not an element of A, we know that C is not a subset of A .

There are 5 elements in set T, so the number of subsets of T is 25, which equals 32.

Set R = <0, 1, 2, 3, 4>and set S = <4, 3, 0, 2, 1>, thus R is equivalent to S.

Universal Set

Each of the elements in set G and set H are integers. None of these elements are fractions nor irrationals.

By definition, sets X and Y are each subsets of the universal set. So the world must be the universal set.

By definition, sets M and N are each subsets of the universal set. The intersection of M and N is null. So all of the above is the correct answer.

Triangles does not overlap with quadrilaterals, but triangles is a subset of the universal set (polygons).

Factors of 36 overlaps with set P , and is a subset of the set of whole numbers less than 40 (the universal set).

Set-Builder Notation

The set of all q such that q is an integer greater than or equal to - 4 and less than 3.

The set of all x such that x is a real number greater than or equal to 4.

Each set listed is equal to "the set of all n such that n is an integer less than 2".

Set builder notation is usually used with infinite sets. Choices 1 and 2 are each finite sets that do not have numbers as their elements. By process of elimination, choice 3 makes sense.

The elements given are real numbers. None of the choices (1-3) are sets with real-number elements.

Complement of a Set

The complement of a set is the set of elements which belong to but which do not belong to A .

X'= n | n and n X >

The complement of set P is the set of elements which belong to but which do not belong to P .

The complement of set N is the set of elements which belong to (the alphabet) but which do not belong to N .

Draw a Venn diagram to help you find the answer.

The complement of set A is the set of elements which belong to but which do not belong to A .

A'= x | x and x A >

Intersection

Oranges and pears are common to both sets.

The number 2 is the only even prime.

These sets have no elements in common.

The number 3 is an element of P , and is not in the intersection of P and Q .

Union

The numbers 0 and 1 are neither prime nor composite.

The union of a set and its complement is the Universal Set.

Practice Exercises

Choice 1 uses set-builder notation, choice 2 describes the set, and choice 3 uses roster notation.

The element - 2 is not an element of set D .

All of the sets listed are finite except choice 4.

X = Y since X and Y contain exactly the same number of elements, and the elements in both are the same.

The element n is not a member of set P . So set S cannot be a subset of set P .

Both triangles ate trapezoids are subsets of polygons.

Choice 2 is the set of q such that q is an element of the integers, and q is greater than or equal to - 5.

A' = x | x and x A >

The shaded region shows a union of sets X and Y .

The shaded region shows an intersection of sets X and Y .

Challenge Exercises

The letters m, a and t are listed more than once, so the objects are not unique.

9 is not an element of C .

Choice 2 is a finite set the rest are infinite.

Choice 3 is equal to the set of n such that n is an element of the integers, and n is greater than or equal to - 3 and less than 7.

There are 5 elements in M, so the number of subsets is 25 which equal 32.

P = <2, 3, 5, 7, 11, 13, 17, 19>and Q = <2, 4, 6, 8, 10, 12, 14, 16, 18>. The element 2 is in the intersection of both sets.

Choice 2 correctly describes the set given in set-builder notation.

Complement of a set is defined as: A ' = x | x and x A >


Post-processing cosmological samples¶

Let’s suppose that we want to importance-reweight a Planck sample, in particular the one we just generated with the input above, with some late time LSS data from BAO. To do that, we add the new BAO likelihoods. We would also like to increase the theory code’s precision with some extra arguments: we will need to re- add it, and set the new precision parameter under extra_args (the old extra_args will be inherited, unless specifically redefined). For his example let’s say we do not need to recompute the CMB likelihoods, so power spectra do not need to be recomputed, but we do want to add a new derived parameter.

Assuming we saved the sample at chains/planck , we need to define the following input file, which we can run with $ cobaya-run :


Set Operations

Much like (+) is an operation on two numbers, the following set operations are binary operators where the operands are sets instead of numbers.

To indicate set inclusion, that one set is contained in another set, the symbol ( subset ) is used. For instance, ( < 1, 2 >) is a subset of ( <1, 2, 3>). This is written as ( < 1, 2 >subset <1, 2, 3>). If the subset has the potential to be equal to the superset, then the symbol ( subseteq ) is used. Though, some authors use the symbol ( subset ) even when equality is possible. When equality is not possible, the term proper subset is used.

More generally, we might visualize a set hierarchy such as ( A subset B subset mathcal ) as follows. Imagine that there are elements in the sets, even if they're not drawn.

The next two operations either combine the contents of two sets, or reference only the elements contained in both sets. These two operations are union ( cup ) and intersection ( cap ), repsectively. Pictures are my preferred strategy for understanding ( cup ) and ( cap ).

Let (A, B subset mathcal ). The union of ( A ) and ( B ), written ( A cup B ), is equal to the set that consists of all elements in either set (counted only once). In set builder notation, ( A cup B = x in B > ). The following display visualizes in blue the set ( color<#00BFFF> ). to addition.

Let (A, B subset mathcal ). The intersection of ( A ) and ( B ), written ( A cap B ), is equal to the set that consists of only the elements in both sets. In set builder notation, (A cap B = x in B > ). The following display visualizes in pink the set ( color<#00B78D> ).

Set difference is the analogue to subtraction. Let (A subset B ). The set difference ( color<#FF6DAE> ) consists of all the elements of ( B ) after removing those elements that are also in ( A ). Think of this as ( B ) remove ( A ).

In another analogy to binary operations on numbers, the symbol ( imes ) when applied to sets is called the Cartesian product. Let ( A, B subset mathcal ). The set ( A imes B = <(a, b) | a in A ext< and >b in B > ), that is the set of ordered pairs that consist of one element from each of the two sets in the product.

Our last set operation is named cardinality. Cardinality measures the number of elements in a set. For the set of suits in a standard deck of cards ( S = < ) &spades, &hearts , &clubs, &diams ( >), the cardinality of ( S ) is ( |S| = 4 ).

A deck of cards is a set of 52 elements. This set can be thought of as the Cartesian product of the two sets ( S = < ) &spades, &hearts , &clubs, &diams ( >) and ( N = < A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K >). Since ( |S| = 4 ) and ( |N| = 13 ), the cardinality of a standard deck of cards ( |D| = |S imes N| = 52 ). This is the thinking behind the analogy between the Cartesian product and multiplication.


An Algorithm a Day

“If its possible to express the world in a set, a mathematician would do that!! :) The power of sets are vast that its used in statistics and computing a lot. To understand algorithms clearly, you need to understand set theory!!”

I am assuming that, the reader already know a little bit about Sets. Sets is a collection of unique objects. There is natural(without negative) number set, real number(floating point) set, integer(with negative) set. You can also have sets with different symbols. But the major operations that can be done between two sets, A & B, are:

  • Intersection: common items between A & B , $AcapB$
  • Union: all unique items between A & B (common items appear only once) $AcupB$
  • Difference: if its, A-B, then items in B if present in A are removed and you get remaining elements.
  • Disjoint: both A & B don’t have any items in common

I assume you understand the above general and basic concepts to move on into More details

Extra concepts which you might require in some problem solving & algorithms are,

  • singleton set: a set with only 1 element in it.
  • partition of a set: a set if gets partitioned into subsets of size>0.. its called a partition. [Check here: http://en.wikipedia.org/wiki/Partition_of_a_set]
  • complement of a set: If you take a set A, complement of set A is the elements which are not present in A. $ar$
  • universal set: $Acupar$ is a universal set which includes all the elements in the bigger set
  • n-set: If you have “n” elements in a set, its called n-set,
  • k-subset: If you have “k” element subset from a “n” element set, its called a k-subset of the bigger set.
  • Cartesian product set: Its the product of two sets.. straight to straight!! A x B = x =
  • binary relation set: subset of Cartesian product between sets. For example, if A & B are subsets in a Natural number set and a relation is defined between the elements in the sets, like, a<b, for a in A, b in B, then, it means, the two sets A & B has elements sorted in ascending order when combined!!
  • equivalence relation between sets: is a type of binary relation set!! but the sets will contain elements which are disjoint and exhibit equivalence among each other. i.e, two sets are equivalence sets only if they are part of a same set under a binary relation
  • equivalence class: the condition of equivalence between two sets should hold in all the elements of the class set. i.e, if you need a set of even numbers from a natural number set given an even number, define a relation such that, equivalence is hold, like a+b is even..
  • functions: extension of Cartesian product. Instead of just Cartesian product, we place a function with a binary relation among elements in the set
  • The main application will be on Graphs!! :) We will study about it soon. We have all the set concepts in a graph!!
  • As it can put in Graph, Tree is just a subset of Graph. Tree concepts are all derived from the set theory!!
  • Binary trees we studied are disjoint sets composed of: root node, left sub tree, right sub tree. Disjoint means, all these 3 sets should have completely different nodes!! It’s not necessary to have any nodes as well. This makes, Binary tree a special case of Trees.
  • Partition of a set can be directly related to substring, subsets in an array etc.

Example: The set < 1, 2, 3 >has these five partitions:

This is clearly how python lists work!! :). Python and Perl both have splice, union, intersection of arrays/lists.


Watch the video: - Getting Started - Project Setup (December 2021).