Articles

0.3: Basic set theory - Mathematics


0.3: Basic set theory - Mathematics

Naive set theory

Sets are arguably the most fundamental objects in modern mathematics. Familiarity with set notation is definitely a requirement for understanding post-secondary mathematics. Furthermore, some mathematicians over the years have demonstrated that most of the mathematics that we encounter can be reduced to set theory! As a result, one version of set theory, called axiomatic set theory, has been used as a possible foundation for mathematics. However, we will be somewhat less ambitious and study naive set theory instead. In naive set theory, we do not have to be too precise about the exact definition of a set.


0.3: Basic set theory - Mathematics

Sets are well-determined collections that are completely characterized by their elements. Thus, two sets are equal if and only if they have exactly the same elements. The basic relation in set theory is that of elementhood, or membership. We write (ain A) to indicate that the object (a) is an element, or a member, of the set (A). We also say that (a) belongs to (A). Thus, a set (A) is equal to a set (B) if and only if for every (a), (ain A) if and only if (ain B). In particular, there is only one set with no elements at all. This set is called, naturally, the empty set, and is represented by the symbol ().

We say that (A) is a subset of (B), written (Asubseteq B), if every element of (A) is an element of (B). Thus, (A=B) if and only if (Asubseteq B) and (Bsubseteq A). Notice that (subseteq A), for every set (A).

Given sets (A) and (B), one can perform some basic operations with them yielding the following sets:

The set (Acup B), called the union of (A) and (B), whose elements are the elements of (A) and the elements of (B).

The set (Acap B), called the intersection of (A) and (B), whose elements are the elements common to (A) and (B).

The set (A-B), called the difference of (A) and (B), whose elements are those elements of (A) that are not members of (B).

It is routine to check that those operations satisfy the following properties:

(A cup (Bcap C)=(Acup B)cap (Acup C))

(A cap (Bcup C)=(Acap B)cup (Acap C))

Given an object (a) we can form the set that has (a) as its only element. This set is denoted by (< a >). More generally, given (a,b,c,ldots), we can form the set having (a,b,c,ldots) as its elements, which we denote by (< a,b,c, ldots>). Of course, we can actually write down all the elements of the set when there are not too many of them. In the case of infinite sets this is clearly not possible.

If (a=b), then (< a,b>=< a>). Also, for any (a) and (b), the pair (< a,b>) is the same as the pair (< b,a>). So, if we wish to take into account the order in which the two elements of a pair are given, we need to find another way of representing the pair. Thus, we define the ordered pair ((a,b)) as the set (< < a>,< a,b>>). One can easily check that two ordered pairs ((a,b)) and ((c,d)) are equal if and only if (a=c) and (b=d). The order is now important, for if (a e b), then ((a,b) e (b,a)).

The Cartesian product (A imes B) of two sets, (A) and (B), is defined as the set of all ordered pairs ((a,b)) such that (ain A) and (bin B).

Having defined ordered pairs, one can now define ordered triples ((a,b,c)) as ((a,(b,c))), or in general ordered (n)-tuples ((a_1,ldots ,a_n)) as ((a_1, (a_2,ldots ,a_n))).

The Cartesian product (A_1 imes ldots imes A_n), of the sets (A_1,ldots , A_n) is the set of all (n)-tuples ((a_1,ldots ,a_n)) such that (a_i in A_i), for every (1leq ileq n). In particular, for (ngeq 2), the (n)-times Cartesian product of a set (A), denoted by (A^n), is the set of all (n)-tuples of elements of (A).

1. Relations

A binary relation on a set (A) is a set of ordered pairs of elements of (A), that is, a subset of (A imes A). In general, an (n)-ary relation on (A) is a subset of (A^n).

A binary relation (R) on a set (A) is called reflexive if ((a,a)in R) for every (ain A). It is called symmetric if ((b,a)in R) whenever ((a,b)in R). And it is called transitive if ((a,c)in R) whenever ((a,b)in R) and ((b,c)in R). A relation that is reflexive, symmetric, and transitive is called an equivalence relation. The identity relation on any set (A) is the paradigmatic example of an equivalence relation. Another example is the relation on the set of all finite sets of natural numbers consisting of all the pairs ((a,b)) such that (a) and (b) have the same number of elements.

If (R) is an equivalence relation on a set (A), and ((a,b)in R), then we say that that (a) and (b) are (R)-equivalent. For every (ain A), the equivalence class of (a), usually denoted by ([a]_R), is the set of all elements of (A) that are (R)-equivalent to (a). The set of all (R)-equivalence classes is called the quotient set and is denoted by (A/R). One can easily check that (A/R) is a partition of (A), that is, no element of (A/R) is empty, any two elements of (A/R) are disjoint, and every (ain A) belongs to (exactly) one element of (A/R), namely the class ([a]_R).

If (R) is a binary relation, then one usually writes (aRb) instead of ((a,b)in R).

A binary relation (R) on a set (A) is called antisymmetric if (a=b) whenever (aRb) and (bRa). A relation (R) on a set (A) that is reflexive, antisymmetric, and transitive, is called a (reflexive) partial order. If we remove from (R) all pairs ((a,a)), for every (ain A), then we get a strict partial order. The (subseteq) relation on any set of sets is an example of a partial order. A partial order on a given set (A) is usually represented by the symbol (leq), and the corresponding strict partial ordering by (<). A partial order (leq) on a set (A) with the additional property that either (aleq b) or (bleq a), for all elements (a) and (b) of (A), is called a total order, or a linear order. The usual orderings of the set (mathbb) of natural numbers, the set (mathbb) of the integers, the set (mathbb) of the rational numbers, or the set (mathbb) of real numbers, are linear orders.

Notice that if (leq) is a linear order on a set (A), and (Bsubseteq A), then (leq cap , B^2) is also a linear order on (B). If (leq) is a linear order on a set (A), then we say that (ain A) is the (leq)-least element of (A) if there is no (bin A) distinct from (a) such that (bleq a). The number (0) is the least element of (mathbb), but (mathbb) has no least element.

A linear order (leq) on a set (A) is a well-order if every non-empty subset of (A) has a (leq)-least element. Equivalently, if there is no infinite strictly descending sequence [ldots < a_2< a_1< a_0] of elements of (A). Thus, the usual ordering of (mathbb) is a well-order. But the usual order on (mathbb) is not, because it has no least element.

2. Functions

A ((1)-ary) function on a set (A) is a binary relation (F) on (A) such that for every (ain A) there is exactly one pair ((a,b)in F). The element (b) is called the value of (F) on (a), and is denoted by (F(a)). And the set (A) is called the domain of (F). The notation (F:A o B) indicates that (F) is a function with domain (A) and values in the set (B). For (ngeq 2), an (n)-ary function on (A) is a function (F:A^n o B), for some (B).

A function (F:A o B) is one-to-one if for all elements (a) and (b) of (A), if (a e b), then (F(a) e F(b)). And is onto if for every (bin B) there is some (ain A) such that (F(a)=b). Finally, (F) is bijective if it is one-to-one and onto. Thus, a bijection (F:A o B) establishes a one-to-one correspondence between the elements of (A) and those of (B), and (A) is bijectable with (B) if there is such a bijection. The identity function on a set (A), denoted by (Id:A o A), and which consists of all the pairs ((a,a)), with (ain A), is trivially a bijection.

Given functions (F:A o B) and (G:B o C), the composition of (F) and (G), written (Gcirc F), is the function (Gcirc F:A o C) whose elements are all pairs ((a,G(F(a)))), where (ain A). If (F) and (G) are bijections, then so is (Gcirc F).

3. Sets and formulas

The formal language of set theory is the first-order language whose only non-logical symbol is the binary relation symbol (in).

Given any formula (varphi(x,y_1,ldots ,y_n)) of the language of set theory, and sets (A,B_1,ldots ,B_n), one can form the set of all those elements of (A) that satisfy the formula (varphi(x,B_1,ldots ,B_n)). This set is denoted by (< ain A: varphi(a,B_1,ldots ,B_n)>). The following are some examples

And if (B) and (C) are subsets of (A), then

Given a subset (Csubseteq A imes B), the projection of (C) (on the first coordinate) is the set

It is not the case, however, that given any formula (varphi(x,y_1,ldots ,y_n)), and sets (B_1,ldots ,B_n), one can form the set of all those sets that satisfy the formula (varphi(x,B_1,ldots ,B_n)). For let (varphi(x)) be the formula (x ot in x). If (A) were the set of all sets that satisfy the formula, then (Ain A) if and only if (A ot in A). A contradiction! This contradiction is known as Russell&rsquos paradox, after Bertrand Russell, who discovered it in 1901 (see the entry on Russell&rsquos paradox).

4. Ordinals

The first ordinal number is (). Given an ordinal (alpha), the next bigger ordinal, called the (immediate) successor of (alpha), is the set (alpha cup < alpha >). Thus, the successor of (alpha) is just the set (alpha) together with one more element, namely, (alpha) itself. The finite ordinal numbers are those obtained by starting with () and repeatedly taking the successor.

In set theory the natural numbers are defined as the finite ordinals. Thus,

Notice that (1=< 0>), (2=< 0,1>), (3=< 0,1,2>), and in general we have (n=< 0,1,2,ldots ,n-1>). So, every natural number (n) is just the set of its predecessors.

A set (A) is finite if there is a one-to-one correspondence between some natural number (n) and the elements of (A), i.e., a bijection (F:n o A), in which case we say that (A) has (n) elements. A set is infinite if it is not finite.

The set of all finite ordinals is denoted by the Greek letter omega ((omega)). Thus, (omega) is just the set (mathbb) of natural numbers. (omega) is also an ordinal, the first infinite ordinal. Notice that (omega) is not the successor of any ordinal, and so it is called a limit ordinal. Once we have (omega) we can continue generating more ordinals by taking its successor (omega cup < omega >), then its successor ((omega cup ) cup >), and so on. All ordinal numbers greater than (0) are produced in this way, namely, either by taking the successor of the last produced ordinal, or, if there is no such last ordinal, by taking the set of all the ordinals produced so far, as in the case of (omega) which yields a new limit ordinal. Note, however, that one cannot take the set of all ordinals, for then this set would be a new limit ordinal, which is impossible, since we already had them all.

As with finite ordinals, every infinite ordinal is just the set of its predecessors. One consequence of this is that the (in) relation is a strict well-order on any set of ordinals. Thus, for any ordinals (alpha) and (eta) we define (alpha <eta) if and only if (alpha in eta). Then the associated reflexive well-order is defined as (alpha leq eta) if and only if (alpha <eta) or (alpha =eta). Let us now observe that (alpha subseteq eta) if and only if (alpha leq eta).

5. Countable and uncountable sets

If (A) is a finite set, there is a bijection (F:n o A) between a natural number (n) and (A). Any such bijection gives a counting of the elements of (A), namely, (F(0)) is the first element of (A), (F(1)) is the second, and so on. Thus, all finite sets are countable. An infinite set (A) is called countable if there is a bijection (F:omega o A) between the set of natural numbers and (A). The set (mathbb) of natural numbers is (trivially) countable. If (A) is an infinite subset of (omega), then (A) is also countable: for let (F:omega o A) be such that (F(n)) is the least element of (A) that is not in the set (< F(m)in A: m< n>). Then (F) is a bijection.

Every infinite subset of a countable set is also countable: for suppose (F:omega o A) is a bijection and (Bsubseteq A) is infinite. Then the set (< nin omega: F(n)in B>) is an infinite subset of (omega), hence countable, and so there is a bijection (G:omega o < nin omega : F(n)in B>). Then the composition function (Fcirc G:omega o B) is a bijection.

The union of a countable set and a finite set is also countable. For given sets (A) and (B), which without loss of generality we may assume they are disjoint, and given bijections (F:omega o A) and (G:n o B), for some (n<omega), let (H:omega o Acup B) be the bijection given by: (H(m)=G(m)), for every (m<n), and (H(m)=F(m-n)), for every (nleq m).

Moreover, the union of two countable sets is also countable: since we have already shown that the union of a countable set and a finite set is also countable, it is enough to see that the union of two disjoint countable sets is also countable. So, suppose (A) and (B) are countable sets and (F:omega o A) and (G:omega o B) are bijections, then the function (H:omega o Acup B) consisting of all pairs ((2n,F(n))), plus all pairs ((2n+1, G(n))) is a bijection.

Thus, the set (mathbb), being the union of two countable sets, namely [mathbbcup < -1,-2,-3,-4,ldots >] is also countable.

The Cartesian product of two infinite countable sets is also countable. For suppose (F:omega o A) and (G:omega o B) are bijections. Then, using the fact that the function (J:omega imes omega o omega) given by (J((m,n))= 2^m(2n+1)-1) is a bijection, one has that the function (H:omega o A imes B) given by (H(2^m(2n+1)-1)=(F(m),G(n))) is also a bijection.

Since any rational number is given by a pair of integers, i.e., a quotient (frac), where (m,nin mathbb) and (n e 0), the set (mathbb) of rational numbers is also countable.

However, Georg Cantor discovered that the set (mathbb) of real numbers is not countable. For suppose, aiming for a contradiction, that (F:omega o mathbb) is a bijection. Let (a_0=F(0)). Choose the least (k) such that (a_0<F(k)) and put (b_0=F(k)). Given (a_n) and (b_n), choose the least (l) such that (a_n<F(l)<b_n), and put (a_=F(l)). And choose the least (m) such that (a_<F(m)<b_n), and put (b_=F(m)). Thus, we have (a_0<a_1<a_2<cdots) (cdots <b_2<b_1<b_0). Now let (a) be the limit of the (a_n). Then (a) is a real number different from (F(n)), all (n), which is impossible because (F) is a bijection.

The existence of uncountable sets follows from a much more general fact, also discovered by Cantor. Namely, given any set (A), the set of all its subsets, called the power set of (A), and denoted by (mathcal

(A)), is not bijectable with (A): for suppose that (F:A o mathcal

(A)) is a bijection. Then the subset (< ain A: a ot in F(a)>) of (A) is the value (F(a)) of some (ain A). But then (ain F(a)) if and only if (a ot in F(a)). Hence, if (A) is any infinite set, then (mathcal

(A)) is uncountable.

There are also uncountable ordinals. The set of all finite and countable ordinals is also an ordinal, called (omega_1), and is the first uncountable ordinal. Similarly, the set of all ordinals that are bijectable with some ordinal less than or equal to (omega_1) is also an ordinal, called (omega_2), and is not bijectable with (omega_1), and so on.

5.1 Cardinals

The cardinality, or size, of a finite set (A) is the unique natural number (n) such that there is a bijection (F:n o A).

In the case of infinite sets, their cardinality is given, not by a natural number, but by an infinite ordinal. However, in contrast with the finite sets, an infinite set (A) is bijectable with many different ordinal numbers. For example, the set (mathbb) is bijectable with (omega), but also with it successor (omega cup ): by assigning (0) to (omega) and (n+1) to (n), for all (nin omega), we obtain a bijection between (omega cup ) and (omega). But since the ordinals are well-ordered, we may define the cardinality of an infinite set as the least ordinal that is bijectable with it.

In particular, the cardinality of an ordinal number (alpha) is the least ordinal (kappa) that is bijectable with it. Notice that (kappa) is not bijectable with any smaller ordinal, for otherwise so would be (alpha). The ordinal numbers that are not bijectable with any smaller ordinal are called cardinal numbers. Thus, all natural numbers are cardinals, and so are (omega), (omega_1), (omega_2), and so on. In general, given any cardinal (kappa), the set of all ordinals that are bijectable with some ordinal (leq kappa) is also a cardinal it is the smallest cardinal bigger than (kappa).

The infinite cardinals are represented by the letter aleph ((aleph)) of the Hebrew alphabet. Thus, the smallest infinite cardinal is (omega =aleph_0), the next one is (omega_1=aleph_1), which is the first uncountable cardinal, then comes (omega_2=aleph_2), etc.

The cardinality of any set (A), denoted by (|A|), is the unique cardinal number that is bijectable with (A). We saw already that (|mathbb|) is uncountable, hence greater than (aleph_0), but it is not known what cardinal number it is. The conjecture that (|mathbb|=aleph_1), formulated by Cantor in 1878, is the famous Continuum Hypothesis.


"Point" of Set Theory?

Well, it's really a dumb question, actually. I'm a third year undergraduate student finishing (as in having just a final exam to go) a course on elementary Set Theory.

When it comes to analysis vs algebra discussions, I'm always on the analysis side, I've enjoyed the probability courses the most, but I also appreciate the abstract ones. Anyhow, although I am able to see the "beauty" behind the fundaments of set theory, I'm not really sure what the answer to the question "WHY am I studying this" is - simply because, for example, ordinal numbers or definition of natural numbers as the sets contained in every inductive set, seem to me as something a mathematician would work on when he's bored. (As in, I don't really see the use of any of it beyond setting the philosophical fundaments of math.)

Yes, this may come out arrogant or something, but I'm really only looking to find the right motivation to learn even more about the field and then finally decide if I like it or not. Seems stupid, yes, but, oh well.

One thing that can make it hard to see why an idea is more than a mathematician doodling for fun is that things are often taught with a very ahistoric perspective. We teach the concepts, but we don't talk about the historical context they arose out of. Ideas in math arise in response to other ideas, but if you aren't shown the context, it can be hard to see why anyone would ever care.

This excellent paper by Kanamori talks about the historical development of set theory, what problems in mathematics gave rise to some of the ideas in set theory, and where the specific constructions came from. It's worth reading, or at least skimming. Section 1, about Cantor's work, including on ordinals, and Sections 3.1 and 3.2, about von Neumann's definition of ordinal and the cumulative hierarchy, might be especially of interest to you.

To briefly answer your question, ordinals are of immense importance to set theory. They show up everywhere. Honestly, it speaks poorly of the class you took that their importance was not conveyed to you. Mathias once quipped that set theory is the study of well-foundedness. Like any one sentence summary of a field, it ignores many subtleties. Nevertheless, there is a lot of truth to it. Ordinals, being the well-founded linear orders, are accordingly of natural importance to set theory.

Let's look at just few uses of ordinals.

At the most basic level, ordinals are the spine of the universe of sets. This is the so-called cumulative hierarchy conception of sets. We start with the empty set and generate all sets by taking progressive powersets, once for each ordinal. Anything that's based upon the cumulative hierarchy, rank, etc. will at some level use ordinals.

Schoenfield's absoluteness theorem implies that sufficiently simple (in a precise, technical sense) statements about the reals are true iff they are true in L, the constructible universe. One specific application of this is that if you can prove a sufficiently simple statement using AC, then it's provable without choice. But it does a lot more: if you can prove a sufficiently simple statement using any of the powerful tools in L: diamond, condensation, GCH, the existence of a global well-order, etc., then actually you can prove them just in ZF. Schoenfield's absoluteness theorem gets a lot of use in set theory. The proof of this theorem uses essentially the properties of ordinals, going through well-founded trees.

For that matter, the construction of L uses ordinals. Gödel once described the construction as "which can be obtained by Russell's ramified hierarchy of types, if extended to include transfinite orders." (Quoted from the Kanamori paper linked above.)

Large parts of descriptive set theory use ordinals. The classical example of this is Borel's construction of the Borel hierarchy. Borel sets are organized into levels, with open and closed sets on the bottom level, and sets on the higher levels coming from countable unions/intersections of sets from previous levels. There are omega_1 many levels, one for each countable ordinal.

For an application outside of set theory, countable ordinals show up in proof theory. An idea, coming from Gentzen, is that we can measure the strength of a proof system by an ordinal, the system's so-called proof theoretic ordinal. The more powerful a proof system is, the larger its proof theoretic ordinal. For example, Peano arithmetic's proof theoretic ordinal is epsilon_0, i.e. the limit of omega, omega omega , omega omega^omega , . Primitive recursive arithmetic, a weak fragment of PA, only has proof theoretic ordinal omega omega .

One other thing I'll say is that set theory doesn't exist just to play a foundational role. A fair number of people write off set theory because they aren't interested in foundations and they are under the misunderstanding that set theory is just about foundations. If you decide you aren't interested in set theory, do so because you aren't interested in the mathematics of set theory, not because you aren't interested in foundations.


The complement of a set, A, refers to the elements that are not in A. Among other notations, the complement of A can be denoted as A c . For example, in a case where all integers are being considered, if A were the set of all even integers A c would be the set of all odd integers.

Sets can be "subtracted." The difference between two sets, A and B, can be denoted as A B. This difference can be referred to as the relative complement of B in A and represents the set of all elements in A that are not in B. This difference can be depicted as the following:

In the context of complements, a universal set, U, can be said to contain all the subsets being discussed. In such a case, U A would be the complement of A. In other words, A c = U A.

Below is a depiction of A c :

The grey area represents the complement of A.


0.3: Basic set theory - Mathematics

A Set is an unordered collection of objects, known as elements or members of the set.
An element ‘a’ belong to a set A can be written as ‘a &in A’, ‘a ¬in A’ denotes that a is not an element of the set A.

Representation of a Set
A set can be represented by various methods. 3 common methods used for representing set:
1. Statement form.
2. Roaster form or tabular form method.
3. Set Builder method.

Statement form
In this representation, the well-defined description of the elements of the set is given. Below are some examples of the same.
1. The set of all even number less than 10.
2. The set of the number less than 10 and more than 1.

Roster form
In this representation, elements are listed within the pair of brackets <> and are separated by commas. Below are two examples.
1. Let N is the set of natural numbers less than 5.
N = < 1 , 2 , 3, 4 >.

2. The set of all vowels in the English alphabet.
V = < a , e , i , o , u >.

Set builder form
In Set-builder set is described by a property that its member must satisfy.
1. .
2. .

Equal sets
Two sets are said to be equal if both have same elements. For example A = <1, 3, 9, 7>and B = <3, 1, 7, 9>are equal sets.

NOTE: Order of elements of a set doesn’t matter.

A set A is said to be subset of another set B if and only if every element of set A is also a part of other set B.
Denoted by ‘&sube‘.
‘A &sube B ‘ denotes A is a subset of B.

To prove A is the subset of B, we need to simply show that if x belongs to A then x also belongs to B.
To prove A is not a subset of B, we need to find out one element which is part of set A but not belong to set B.

‘U’ denotes the universal set.
Above Venn Diagram shows that A is a subset of B.

Size of a Set
Size of a set can be finite or infinite.

Size of the set S is known as Cardinality number, denoted as |S|.

Example: Let A be a set of odd positive integers less than 10.
Solution : A = <1,3,5,7,9>, Cardinality of the set is 5, i.e.,|A| = 5.

Note: Cardinality of a null set is 0.

Power Sets
The power set is the set all possible subset of the set S. Denoted by P(S).
Example: What is the power set of <0,1,2>?
Solution: All possible subsets
<&empty>, <0>, <1>, <2>, <0,1>, <0,2>, <1,2>, <0,1,2>.
Note: Empty set and set itself is also the member of this set of subsets.

Cardinality of power set is

, where n is the number of elements in a set.

Cartesian Products
Let A and B be two sets. Cartesian product of A and B is denoted by A × B, is the set of all ordered pairs (a,b), where a belong to A and b belong to B.

Example 1. What is Cartesian product of A = <1,2>and B = .
Solution : A × B =<(1, p), (1, q), (1, r), (2, p), (2, q), (2, r) >


The cardinality of A × B
is N*M, where N is the Cardinality of A and M is the cardinality of B.

Note: A × B is not the same as B × A.

Below are some Gate Previous question

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Attention reader! Don&rsquot stop learning now. Learn all GATE CS concepts with Free Live Classes on our youtube channel.


Contents

Mathematical topics typically emerge and evolve through interactions among many researchers. Set theory, however, was founded by a single paper in 1874 by Georg Cantor: "On a Property of the Collection of All Real Algebraic Numbers". [2] [3]

Since the 5th century BC, beginning with Greek mathematician Zeno of Elea in the West and early Indian mathematicians in the East, mathematicians had struggled with the concept of infinity. Especially notable is the work of Bernard Bolzano in the first half of the 19th century. [4] Modern understanding of infinity began in 1870–1874, and was motivated by Cantor's work in real analysis. [5] An 1872 meeting between Cantor and Richard Dedekind influenced Cantor's thinking, and culminated in Cantor's 1874 paper.

Cantor's work initially polarized the mathematicians of his day. While Karl Weierstrass and Dedekind supported Cantor, Leopold Kronecker, now seen as a founder of mathematical constructivism, did not. Cantorian set theory eventually became widespread, due to the utility of Cantorian concepts, such as one-to-one correspondence among sets, his proof that there are more real numbers than integers, and the "infinity of infinities" ("Cantor's paradise") resulting from the power set operation. This utility of set theory led to the article "Mengenlehre", contributed in 1898 by Arthur Schoenflies to Klein's encyclopedia.

The next wave of excitement in set theory came around 1900, when it was discovered that some interpretations of Cantorian set theory gave rise to several contradictions, called antinomies or paradoxes. Bertrand Russell and Ernst Zermelo independently found the simplest and best known paradox, now called Russell's paradox: consider "the set of all sets that are not members of themselves", which leads to a contradiction since it must be a member of itself and not a member of itself. In 1899, Cantor had himself posed the question "What is the cardinal number of the set of all sets?", and obtained a related paradox. Russell used his paradox as a theme in his 1903 review of continental mathematics in his The Principles of Mathematics.

In 1906, English readers gained the book Theory of Sets of Points [6] by husband and wife William Henry Young and Grace Chisholm Young, published by Cambridge University Press.

The momentum of set theory was such that debate on the paradoxes did not lead to its abandonment. The work of Zermelo in 1908 and the work of Abraham Fraenkel and Thoralf Skolem in 1922 resulted in the set of axioms ZFC, which became the most commonly used set of axioms for set theory. The work of analysts, such as that of Henri Lebesgue, demonstrated the great mathematical utility of set theory, which has since become woven into the fabric of modern mathematics. Set theory is commonly used as a foundational system, although in some areas—such as algebraic geometry and algebraic topology—category theory is thought to be a preferred foundation.

Set theory begins with a fundamental binary relation between an object o and a set A . If o is a member (or element) of A , the notation oA is used. [7] A set is described by listing elements separated by commas, or by a characterizing property of its elements, within braces < >. [8] Since sets are objects, the membership relation can relate sets as well.

A derived binary relation between two sets is the subset relation, also called set inclusion. If all the members of set A are also members of set B , then A is a subset of B , denoted AB . [7] For example, <1, 2>is a subset of <1, 2, 3>, and so is <2>but <1, 4>is not. As implied by this definition, a set is a subset of itself. For cases where this possibility is unsuitable or would make sense to be rejected, the term proper subset is defined. A is called a proper subset of B if and only if A is a subset of B , but A is not equal to B . Also, 1, 2, and 3 are members (elements) of the set <1, 2, 3>, but are not subsets of it and in turn, the subsets, such as <1>, are not members of the set <1, 2, 3>.

Just as arithmetic features binary operations on numbers, set theory features binary operations on sets. [9] The following is a partial list of them:

  • Union of the sets A and B , denoted AB , [7] is the set of all objects that are a member of A , or B , or both. [10] For example, the union of <1, 2, 3>and <2, 3, 4>is the set <1, 2, 3, 4>.
  • Intersection of the sets A and B , denoted AB , [7] is the set of all objects that are members of both A and B . For example, the intersection of <1, 2, 3>and <2, 3, 4>is the set <2, 3>.
  • Set difference of U and A , denoted U A , is the set of all members of U that are not members of A . The set difference <1, 2, 3> <2, 3, 4>is <1>, while conversely, the set difference <2, 3, 4> <1, 2, 3>is <4>. When A is a subset of U , the set difference U A is also called the complement of A in U . In this case, if the choice of U is clear from the context, the notation Ac is sometimes used instead of U A , particularly if U is a universal set as in the study of Venn diagrams.
  • Symmetric difference of sets A and B , denoted AB or AB , [7] is the set of all objects that are a member of exactly one of A and B (elements which are in one of the sets, but not in both). For instance, for the sets <1, 2, 3>and <2, 3, 4>, the symmetric difference set is <1, 4>. It is the set difference of the union and the intersection, (AB) (AB) or (A B) ∪ (B A) .
  • Cartesian product of A and B , denoted A × B , [7] is the set whose members are all possible ordered pairs (a, b) , where a is a member of A and b is a member of B . For example, the Cartesian product of <1, 2>and is <(1, red), (1, white), (2, red), (2, white)>.
  • Power set of a set A , denoted P ( A ) >(A)> , [7] is the set whose members are all of the possible subsets of A . For example, the power set of <1, 2>is < <>, <1>, <2>, <1, 2>> .

Some basic sets of central importance are the set of natural numbers, the set of real numbers and the empty set—the unique set containing no elements. The empty set is also occasionally called the null set, [11] though this name is ambiguous and can lead to several interpretations.

A set is pure if all of its members are sets, all members of its members are sets, and so on. For example, the set <<>> containing only the empty set is a nonempty pure set. In modern set theory, it is common to restrict attention to the von Neumann universe of pure sets, and many systems of axiomatic set theory are designed to axiomatize the pure sets only. There are many technical advantages to this restriction, and little generality is lost, because essentially all mathematical concepts can be modeled by pure sets. Sets in the von Neumann universe are organized into a cumulative hierarchy, based on how deeply their members, members of members, etc. are nested. Each set in this hierarchy is assigned (by transfinite recursion) an ordinal number α , known as its rank. The rank of a pure set X is defined to be the least upper bound of all successors of ranks of members of X . For example, the empty set is assigned rank 0, while the set <<>> containing only the empty set is assigned rank 1. For each ordinal α , the set V α > is defined to consist of all pure sets with rank less than α . The entire von Neumann universe is denoted V .

Elementary set theory can be studied informally and intuitively, and so can be taught in primary schools using Venn diagrams. The intuitive approach tacitly assumes that a set may be formed from the class of all objects satisfying any particular defining condition. This assumption gives rise to paradoxes, the simplest and best known of which are Russell's paradox and the Burali-Forti paradox. Axiomatic set theory was originally devised to rid set theory of such paradoxes. [note 1]

The most widely studied systems of axiomatic set theory imply that all sets form a cumulative hierarchy. Such systems come in two flavors, those whose ontology consists of:

    Sets alone. This includes the most common axiomatic set theory, Zermelo–Fraenkel set theory with the Axiom of Choice (ZFC). Fragments of ZFC include:
      , which replaces the axiom schema of replacement with that of separation , a small fragment of Zermelo set theory sufficient for the Peano axioms and finite sets , which omits the axioms of infinity, powerset, and choice, and weakens the axiom schemata of separation and replacement.

    The above systems can be modified to allow urelements, objects that can be members of sets but that are not themselves sets and do not have any members.

    The New Foundations systems of NFU (allowing urelements) and NF (lacking them) are not based on a cumulative hierarchy. NF and NFU include a "set of everything", relative to which every set has a complement. In these systems urelements matter, because NF, but not NFU, produces sets for which the axiom of choice does not hold.

    Systems of constructive set theory, such as CST, CZF, and IZF, embed their set axioms in intuitionistic instead of classical logic. Yet other systems accept classical logic but feature a nonstandard membership relation. These include rough set theory and fuzzy set theory, in which the value of an atomic formula embodying the membership relation is not simply True or False. The Boolean-valued models of ZFC are a related subject.

    An enrichment of ZFC called internal set theory was proposed by Edward Nelson in 1977.

    Many mathematical concepts can be defined precisely using only set theoretic concepts. For example, mathematical structures as diverse as graphs, manifolds, rings, and vector spaces can all be defined as sets satisfying various (axiomatic) properties. Equivalence and order relations are ubiquitous in mathematics, and the theory of mathematical relations can be described in set theory.

    Set theory is also a promising foundational system for much of mathematics. Since the publication of the first volume of Principia Mathematica, it has been claimed that most (or even all) mathematical theorems can be derived using an aptly designed set of axioms for set theory, augmented with many definitions, using first or second-order logic. For example, properties of the natural and real numbers can be derived within set theory, as each number system can be identified with a set of equivalence classes under a suitable equivalence relation whose field is some infinite set.

    Set theory as a foundation for mathematical analysis, topology, abstract algebra, and discrete mathematics is likewise uncontroversial mathematicians accept (in principle) that theorems in these areas can be derived from the relevant definitions and the axioms of set theory. However, it remains that few full derivations of complex mathematical theorems from set theory have been formally verified, since such formal derivations are often much longer than the natural language proofs mathematicians commonly present. One verification project, Metamath, includes human-written, computer-verified derivations of more than 12,000 theorems starting from ZFC set theory, first-order logic and propositional logic.

    Set theory is a major area of research in mathematics, with many interrelated subfields.

    Combinatorial set theory Edit

    Combinatorial set theory concerns extensions of finite combinatorics to infinite sets. This includes the study of cardinal arithmetic and the study of extensions of Ramsey's theorem such as the Erdős–Rado theorem.

    Descriptive set theory Edit

    Descriptive set theory is the study of subsets of the real line and, more generally, subsets of Polish spaces. It begins with the study of pointclasses in the Borel hierarchy and extends to the study of more complex hierarchies such as the projective hierarchy and the Wadge hierarchy. Many properties of Borel sets can be established in ZFC, but proving these properties hold for more complicated sets requires additional axioms related to determinacy and large cardinals.

    The field of effective descriptive set theory is between set theory and recursion theory. It includes the study of lightface pointclasses, and is closely related to hyperarithmetical theory. In many cases, results of classical descriptive set theory have effective versions in some cases, new results are obtained by proving the effective version first and then extending ("relativizing") it to make it more broadly applicable.

    A recent area of research concerns Borel equivalence relations and more complicated definable equivalence relations. This has important applications to the study of invariants in many fields of mathematics.

    Fuzzy set theory Edit

    In set theory as Cantor defined and Zermelo and Fraenkel axiomatized, an object is either a member of a set or not. In fuzzy set theory this condition was relaxed by Lotfi A. Zadeh so an object has a degree of membership in a set, a number between 0 and 1. For example, the degree of membership of a person in the set of "tall people" is more flexible than a simple yes or no answer and can be a real number such as 0.75.

    Inner model theory Edit

    An inner model of Zermelo–Fraenkel set theory (ZF) is a transitive class that includes all the ordinals and satisfies all the axioms of ZF. The canonical example is the constructible universe L developed by Gödel. One reason that the study of inner models is of interest is that it can be used to prove consistency results. For example, it can be shown that regardless of whether a model V of ZF satisfies the continuum hypothesis or the axiom of choice, the inner model L constructed inside the original model will satisfy both the generalized continuum hypothesis and the axiom of choice. Thus the assumption that ZF is consistent (has at least one model) implies that ZF together with these two principles is consistent.

    The study of inner models is common in the study of determinacy and large cardinals, especially when considering axioms such as the axiom of determinacy that contradict the axiom of choice. Even if a fixed model of set theory satisfies the axiom of choice, it is possible for an inner model to fail to satisfy the axiom of choice. For example, the existence of sufficiently large cardinals implies that there is an inner model satisfying the axiom of determinacy (and thus not satisfying the axiom of choice). [12]

    Large cardinals Edit

    A large cardinal is a cardinal number with an extra property. Many such properties are studied, including inaccessible cardinals, measurable cardinals, and many more. These properties typically imply the cardinal number must be very large, with the existence of a cardinal with the specified property unprovable in Zermelo–Fraenkel set theory.

    Determinacy Edit

    Determinacy refers to the fact that, under appropriate assumptions, certain two-player games of perfect information are determined from the start in the sense that one player must have a winning strategy. The existence of these strategies has important consequences in descriptive set theory, as the assumption that a broader class of games is determined often implies that a broader class of sets will have a topological property. The axiom of determinacy (AD) is an important object of study although incompatible with the axiom of choice, AD implies that all subsets of the real line are well behaved (in particular, measurable and with the perfect set property). AD can be used to prove that the Wadge degrees have an elegant structure.

    Forcing Edit

    Paul Cohen invented the method of forcing while searching for a model of ZFC in which the continuum hypothesis fails, or a model of ZF in which the axiom of choice fails. Forcing adjoins to some given model of set theory additional sets in order to create a larger model with properties determined (i.e. "forced") by the construction and the original model. For example, Cohen's construction adjoins additional subsets of the natural numbers without changing any of the cardinal numbers of the original model. Forcing is also one of two methods for proving relative consistency by finitistic methods, the other method being Boolean-valued models.

    Cardinal invariants Edit

    A cardinal invariant is a property of the real line measured by a cardinal number. For example, a well-studied invariant is the smallest cardinality of a collection of meagre sets of reals whose union is the entire real line. These are invariants in the sense that any two isomorphic models of set theory must give the same cardinal for each invariant. Many cardinal invariants have been studied, and the relationships between them are often complex and related to axioms of set theory.

    Set-theoretic topology Edit

    Set-theoretic topology studies questions of general topology that are set-theoretic in nature or that require advanced methods of set theory for their solution. Many of these theorems are independent of ZFC, requiring stronger axioms for their proof. A famous problem is the normal Moore space question, a question in general topology that was the subject of intense research. The answer to the normal Moore space question was eventually proved to be independent of ZFC.

    From set theory's inception, some mathematicians have objected to it as a foundation for mathematics. The most common objection to set theory, one Kronecker voiced in set theory's earliest years, starts from the constructivist view that mathematics is loosely related to computation. If this view is granted, then the treatment of infinite sets, both in naive and in axiomatic set theory, introduces into mathematics methods and objects that are not computable even in principle. The feasibility of constructivism as a substitute foundation for mathematics was greatly increased by Errett Bishop's influential book Foundations of Constructive Analysis. [13]

    A different objection put forth by Henri Poincaré is that defining sets using the axiom schemas of specification and replacement, as well as the axiom of power set, introduces impredicativity, a type of circularity, into the definitions of mathematical objects. The scope of predicatively founded mathematics, while less than that of the commonly accepted Zermelo–Fraenkel theory, is much greater than that of constructive mathematics, to the point that Solomon Feferman has said that "all of scientifically applicable analysis can be developed [using predicative methods]". [14]

    Ludwig Wittgenstein condemned set theory philosophically for its connotations of Mathematical platonism. [15] He wrote that "set theory is wrong", since it builds on the "nonsense" of fictitious symbolism, has "pernicious idioms", and that it is nonsensical to talk about "all numbers". [16] Wittgenstein identified mathematics with algorithmic human deduction [17] the need for a secure foundation for mathematics seemed, to him, nonsensical. [18] Moreover, since human effort is necessarily finite, Wittgenstein's philosophy required an ontological commitment to radical constructivism and finitism. Meta-mathematical statements — which, for Wittgenstein, included any statement quantifying over infinite domains, and thus almost all modern set theory — are not mathematics. [19] Few modern philosophers have adopted Wittgenstein's views after a spectacular blunder in Remarks on the Foundations of Mathematics: Wittgenstein attempted to refute Gödel's incompleteness theorems after having only read the abstract. As reviewers Kreisel, Bernays, Dummett, and Goodstein all pointed out, many of his critiques did not apply to the paper in full. Only recently have philosophers such as Crispin Wright begun to rehabilitate Wittgenstein's arguments. [20]

    Category theorists have proposed topos theory as an alternative to traditional axiomatic set theory. Topos theory can interpret various alternatives to that theory, such as constructivism, finite set theory, and computable set theory. [21] [22] Topoi also give a natural setting for forcing and discussions of the independence of choice from ZF, as well as providing the framework for pointless topology and Stone spaces. [23]

    An active area of research is the univalent foundations and related to it homotopy type theory. Within homotopy type theory, a set may be regarded as a homotopy 0-type, with universal properties of sets arising from the inductive and recursive properties of higher inductive types. Principles such as the axiom of choice and the law of the excluded middle can be formulated in a manner corresponding to the classical formulation in set theory or perhaps in a spectrum of distinct ways unique to type theory. Some of these principles may be proven to be a consequence of other principles. The variety of formulations of these axiomatic principles allows for a detailed analysis of the formulations required in order to derive various mathematical results. [24] [25]

    As set theory gained popularity as a foundation for modern mathematics, there has been support for the idea of introducing the basics of naive set theory early in mathematics education.

    In the US in the 1960s, the New Math experiment aimed to teach basic set theory, among other abstract concepts, to primary school students, but was met with much criticism. The math syllabus in European schools followed this trend, and currently includes the subject at different levels in all grades. Venn diagrams are widely employed to explain basic set-theoretic relationships to primary school students (even though John Venn originally devised them as part of a procedure to assess the validity of inferences in term logic).

    Set theory is used to introduce students to logical operators (NOT, AND, OR), and semantic or rule description (technically intensional definition [26] ) of sets (e.g. "months starting with the letter A"), which may be useful when learning computer programming, since boolean logic is used in various programming languages. Likewise, sets and other collection-like objects, such as multisets and lists, are common datatypes in computer science and programming.

    In addition to that, sets are commonly referred to in mathematical teaching when talking about different types of numbers ( N , Z , R , . ), and when defining a mathematical function as a relation from one set (the domain) to another set (the range).


    Basic Set Theory

    The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

    This book, a Dover reprint of a text first published by Springer in 1979, is a very rigorous and quite sophisticated introduction to axiomatic set theory. Given both the selection of some of the contents and the way in which this content is presented, this book&rsquos title gives a whole new meaning to the term &ldquobasic.&rdquo

    The book is divided into two parts. Part I (&ldquoPure Set Theory&rdquo) covers an axiomatic introduction to Zermelo-Frankel set theory, both with and without the Axiom of Choice (denoted ZFC and ZF, respectively). Topics covered include cardinal and ordinal numbers and their arithmetic, as well as the Axiom of Choice and a number of its equivalents and alternatives. Part II (&ldquoApplications and Advanced Topics&rdquo) discusses ways in which set theory is used (for example, in topology) and also looks at more sophisticated topics in set theory. More about this shortly.

    Some of the material in Part I is in some sense &ldquobasic,&rdquo but the way in which it is presented here is not. Although the back-cover blurb advertises this book, as back-cover blurbs inevitably do, as being &ldquo[g]eared toward upper-level undergraduate and graduate students,&rdquo I view this book as being wholly unsuitable as a text for an undergraduate course at an average university. The author&rsquos writing style is succinct, and illustrative examples are few and far between. Learning the axioms of set theory from this text is a much more complicated matter than, say, seeing an axiomatic development of group theory or linear algebra. Some of this may be inherent in the nature of the subject matter, but much of it is attributable to the very sophisticated level at which the author approaches things.

    For example: many books on axiomatic set theory begin with an introductory (&ldquonaïve&rdquo) account, to help motivate what follows. There is none of that here the author simply begins with a discussion of &ldquosets&rdquo versus &ldquoclasses&rdquo. This all takes place very early in the text (the first ten pages or so), even before the axioms of ZF and ZFC have been set out.

    In addition, the author uses the language of first order predicate logic with equality to discuss the axioms, and this sometimes results in very complicated-looking expressions that will undoubtedly be confusing to beginning students. The &ldquoschema of replacement&rdquo that appears on page 30, for example, which is much too cumbersome for me to reproduce here, takes one full line of text to write out. The use of first order logic to write the axioms of set theory is certainly not uncommon, but seems unsuitable for students with little background in logic: I can&rsquot help but believe that such students would be overwhelmed by much of the discussion here.

    Additionally, a considerable amount of the material in Part I of the book is certainly not what I would call &ldquobasic&rdquo. Indeed, there are, particularly in chapter V, some results that were, in 1979 when the book was originally published, only a few years old.

    Part II of the text covers some advanced topics in set theory and also looks at ways in which set theory is applied to other areas of mathematics. The first chapter in this part is a very rapid (about 15 pages long) overview of point set topology, essentially devoid of proofs (except for one or two results where some brief hint of a proof is given). This chapter seems to be intended as background for some of the material in the next two chapters, the first of which discusses the real numbers and real spaces. Following an exceptionally succinct (four page long) description of the integers, rational numbers and real numbers, the author also introduces Cantor space and Baire space and discusses the topological and set-theoretical structure of them and the real numbers. Chapters like these two are not common in beginning set theory textbooks, but there may be some benefit in indicating how set theory impacts these topics.

    The next chapter introduces Boolean algebras (&ldquonot a part of set theory proper, but &hellip an off and on companion to set theory&rdquo), starting with the definition. Applications to topology are given (Tychonoff&rsquos theorem is proved using filters and assuming the Axiom of Choice, and then later it is stated, with a proof sketched, that this theorem is actually equivalent to the Axiom of Choice), and related topics in set theory such as Martin&rsquos axiom (a statement implied by the continuum hypothesis, but not itself provable in ZF, hence viewable as a weaker version of the continuum hypothesis) are introduced.

    The final chapter in the text is on infinite combinatorics and large cardinals. An introduction to constructible sets is given, but the subject is not pursued in depth. People interested in a somewhat more accessible introduction to some of these ideas can also consult the last third of Combinatorics and Graph Theory by Harris, Hirst and Mossinghoff (which lists Levy in the bibliography as a &ldquomore technical&rdquo reference).

    Though not, as I have said, suitable for undergraduates, the Levy book may fare better as a possible text for reasonably sophisticated graduate students (although it does deliberately omit some topics, such as model theory and forcing, that one might want to cover in such a course), and also provides a valuable reference for mathematics professionals in other specialties. In this regard, I was particularly impressed by two stylistic decisions made by the author. One was to include, after the statement of many definitions or theorems, a reference to the name of the person responsible, and the date of discovery or creation. (This is how I, a non-expert in set theory if ever there was one, was able to confidently assert, earlier in this review, that some of the results established here were proved just a few years before the text was originally published.)

    Another nice feature is the inclusion of the phrase &ldquoAc&rdquo before the statement of any theorem whose proof requires the Axiom of Choice. However, although the author spends some time discussing weaker versions of this Axiom, he does not distinguish between the full axiom and any weaker versions when annotating theorems in this fashion.

    The book contains a fairly large number of exercises, scattered throughout the body of the text. There are no back-of-the-book solutions, but some of the more difficult ones have hints added to them.

    I previously mentioned that the original Springer text was published in 1979. This Dover reprint was published in 2002. While the body of the text is basically unchanged, a six-page Appendix of additions and corrections has been added at the end, along with a one-page update to the original (quite extensive) bibliography.

    To summarize and conclude: this is not a book for beginners to learn this material from for the first time, but people with some background and sophistication in the area should find much of value here. Levy&rsquos expertise in this area is well-known, and he has obviously given a great deal of thought to how to present this material. This is certainly a book that belongs in any good college library.


    Working with Sets

    Just as numbers can be added, subtracted, multiplied and divided, there are four basic operations for sets:

    Union, Intersection, Relative complement and Complement

    We can look at each of these using three sets:

    Union

    Union is like adding. The union of two sets is their combined elements, that is, all the elements that are in either set. The symbol for union is .

    When the same number appears in both sets, you only need to include it once in the union set.

    The union of any set with itself is itself, A ∪ A = A.

    The union of any set with the empty set is also itself, A ∪ ∅ = A

    Intersection

    The intersection between two sets is the elements that they have in common. The symbol for intersection is .

    Using the three sets above:

    A ∩ C = <1, 2, 4, 7>∩ <5, 10, 15, 20>= <>. In other words, there are no elements in common, so the intersection is the empty set.

    Relative Complement

    If union is like addition, relative complement is a bit like subtraction. The symbol for it is the minus sign, −.

    You start with the first set and take out every element that appears in the second set as well.

    You do NOT end up with all the elements that are only in one or the other!

    The reverse complement is ONLY those elements of the first set that are NOT also in the second set.

    In each case, the only number that is in both is 2, so that is the only number that is removed from the first set.

    Complement

    The complement of a set is everything that is not in it. This is where the universal set comes in useful, because the complement is U (the universal set) – the set you are working with.

    The symbol for complement is &lsquo, so you would write A&lsquo or B&lsquo for the sets above.

    Complement and Reverse Complement

    Both complement and reverse complement are very similar to subtraction BUT

    • To get the complement of a set, you subtract the set from the universal set.
    • To get the reverse complement of a set, you subtract it from another defined set.

    In conclusion…

    Sets may not seem very useful on a day-to-day basis. However, they are extremely useful for higher mathematics, so bear with them. It&rsquos good to understand the basics, so that you can come back to them later if necessary.


    Watch the video: Basic Set Theory, Part 1 (October 2021).