Number sets test. Methods for defining sets

Test on the topic "Sets"

INSTRUCTIONS:

Option 1

1. Determine which of the sets is a subset of A = (10, 20, 30, 40, 50, 60)

a) (10, 20, 30, 40, 50, 60, 70) b) (10) c) (10, 35)

2. Which of the sets determines if A = (1, 2, 3, 4, 5), B = (3, 4, 5, 6, 7)

a) (1, 4, 5) b) (1, 2, 3, 4, 5) c) (1, 2, 3, 4, 5, 6, 7)

if A = (1, 3, 5, 7, 9), B = (1, 2, 3, 4)

a) (1, 3, 5, 7) b) (1, 2, 3, 4, 5, 7, 9) c) (1, 3)

4. The set of triangles was divided into subsets of versatile triangles, isosceles triangles and equilateral triangles... Has the set of triangles been split into classes?

a) yes b) no

5. Which figure shows the union of the sets A and B ()?

Test on the topic "Sets"

Test with the choice of the correct answer.

INSTRUCTIONS: Choose the letter with the correct answer and enter it on the answer sheet.

Option 2

1. Determine which of the sets is a subset

A = (5, 15, 25, 35, 45, 55)

a) (55) b) (5, 25, 50) c) (25, 55, 75)

2. Which of the sets determines if A = (2, 4, 6, 8, 10), B = (8, 10, 12, 14)

a) (2, 4, 6, 8, 10, 12, 14) b) (8, 10, 12, 14) c) (8, 10)

3. Which of the sets determines
if A = (2, 4, 6, 8, 10), B = (2, 4, 8, 9)

a) (2, 4, 6, 8, 10) b) (2, 4, 8, 9) c) (2, 4, 8)

4. The set of all angles was divided into subsets of straight, obtuse and acute. Has the set of angles been split into classes?

a) yes b) no

5. Which figure shows the intersection of the sets A and B (
)?

Federal Agency for Education

Chuvash State University them. I.N. Ulyanov

Alatyr branch

Faculty of Management and Economics

Department of Higher Mathematics and information technologies

Course work

by discipline: Mathematical logic

Elements of set theory

Is done by a student

1 course

groups - AFT 61-06

scientific adviser

prof. A. V. Merlin

Introduction

Set theory – a branch of mathematics that studies the general properties of sets. Set theory is at the core of most mathematical disciplines; she had a profound influence on the understanding of the subject matter of mathematics itself.

Until the second half of the XIX century the concept of "set" was not considered as a mathematical one (many books on the shelf, many human virtues, etc. - all these are purely everyday expressions of speech). The situation changed when the German mathematician Georg Cantor (Fig. 1) developed his program for the standardization of mathematics, within the framework of which any mathematical object had to be one or another "set".

For example, a natural number, according to Cantor, should be considered as a set consisting of a single element of another set, called the "natural series" - which, in turn, is itself a set that satisfies the so-called Peano's axioms. Wherein general concept"Set", which he considered as central to mathematics, Cantor gave little defining definitions such as "a set is a lot that can be thought of as a single", etc. This was quite consistent with the mentality of Cantor himself, who emphasized calling his program not "set theory" (this term appeared much later), and teaching about the sets ( Mengenlehre).

Cantor's program provoked strong protests from many of the leading mathematicians of his day. Leopold Kronecker was especially distinguished by his irreconcilable attitude towards her, who believed that only natural numbers and that which directly reduces to them can be considered mathematical objects (his phrase is known that "God created natural numbers, and everything else is the work of human hands" ). Nevertheless, several other mathematicians - notably Gottlob Frege and David Hilbert - supported Cantor in his intention to translate all mathematics into set-theoretic language.

However, it soon became clear that Cantor's attitude to unlimited arbitrariness when operating with sets (which he himself expressed in the principle “the essence of mathematics consists in its freedom”) is initially flawed. Namely, a number of set-theoretic antinomies were discovered: it turned out that when using set-theoretic representations, some statements can be proved together with their negations (and then, according to the rules of classical propositional logic, absolutely any statement can be "proved"!). The antinomies marked the complete failure of Cantor's program.

Yet Cantor is considered the founder of set theory, and made major contributions to modern mathematics. He owns the following characteristic of the concept "set": A set is the union of certain, different objects, called elements of a set, into a single whole.

Chapter 1. Sets

1.1 Elements and sets

The concepts of a set and an element of a set refer to concepts that are not explicitly defined, such as, for example, a point and a line. The words "collection", "family", "system", "set", etc. - synonyms for the word "set". This is due to the fact that some concepts in mathematics should be initial, serve as those "bricks" that make up general theory... We only determine how these initial concepts relate, not to mention the nature of the objects in question. Human thinking is designed in such a way that the world is represented as consisting of separate "objects". It has long been clear to philosophers that the world is a single indissoluble whole, and the selection of objects in it is nothing more than an arbitrary act of our thinking, which allows us to form a picture of the world available for rational analysis. But be that as it may, the selection of objects and their aggregates is a natural (or even the only possible) way of organizing our thinking, so it is not surprising that it underlies the main tool for describing exact knowledge - mathematics.

We can say that a bunch of - it is any definite collection of objects. The objects of which the set is composed are called it elements. The elements of a set are distinct and distinguishable from each other. Examples of sets can be: many people, animals, plants on our planet, as well as many N natural numbers 1, 2, 3, ..., the set P prime numbers 2, 3, 5, 7, 11, ... The set Z of integers: ..., -2, -1, 0, 1, 2, ..., the set R of real numbers, etc. A set that contains no elements is called empty. Notation: Æ. An empty set is a subset of any set. The cardinality of an empty set is zero. The concept of an empty set (like the concept of "zero") arises from the need for the result of any operation on sets to be also a set.

Usually, in concrete reasoning, the elements of all sets are taken from some one, sufficiently wide set U, which is called a universal set (or universe).

If the object x is an element of the set M, then x is said to belong to M. Notation: xÎM. Otherwise, they say that x does not belong to M. Notation: xÏM. Note that the elements of a set can themselves be sets. For example, many groups of students are made up of elements (groups), which in turn are made up of students.

Let there be given two sets A and B (Figure 1.1.1), then:

Subset – part concept in set theory. The set C is a subset of the set B (Fig. 1.1.1, denoted by CÌB) if each element of the set C is also an element of the set B. For example, the set of all even numbers is a subset of the set of all integers. If C is a subset of B, then B is called a superset of C.

Usually, sets are denoted by capital letters of the Latin alphabet, and the elements of sets are lowercase letters.

The concepts of set, element and belonging, which at first glance seem intuitively clear, on closer examination, lose such clarity. First, the distinguishability of the elements is problematic. For example, the symbols "e" and "a" that appear on this page are one element of the set A or two different elements? Secondly, it is problematic to be able (without additional effort) to indicate whether a given element belongs to a given set. For example, is the number 86958476921537485067857467 prime?

Sets, like objects, can be elements of other sets. A set whose elements are sets is usually called class or family.

Families of sets are usually denoted by uppercase "handwritten" letters of the Latin alphabet to distinguish them from sets that do not contain sets as elements.

1.2 Methods for defining sets

The irrationality of numbers has put us in front of the need to work with infinite sets. But in fact, you have to deal with infinity all the time, for example, any geometric figure - many points: a segment, a circle, a trapezoid, a cone ... - all these figures contain an infinite number of points. Based on this, it becomes necessary to define sets for the convenience of working with them. To define a set, you need to indicate which elements belong to it. This can be done in a variety of ways. We indicate the two most common forms of specifying (defining) sets

Enumeration of elements, that is, an indication of all the elements of the set, which are usually enclosed in curly braces. If the elements: Ò, Â,, À, w - belong to the set M, then we write M = (Ò, Â, Á, À, w);

A characteristic property, when among the elements of a set, by means of a statement, elements that have a certain property (characterizing this set) are distinguished. Let P (x) be some property of the number x. Then the notation (x | P (x)) means the set of all such numbers that have the P (x) property. For example, the set (x | x2 - 3x + 2 = 0) is a set of roots of the equation x2 - 3x + 2 = 0, that is, this set consists of two elements: 2 and 1; (x | 3 12 and x<3} = Æ;

However, when specifying sets in one or the other way, problems can arise. For example, let the set A consist of the Russian words “table”, “world” and the symbol “$” in standard symbols, that is, A = (table, world, $). The set A ^, consisting of the same characters, but in English, will be different A ^ = (table, peace, $). So you need to be precise in enumeration (that is, specifying sets by enumeration). And one more example related to any textbook or book. There are many copies of a book, if we mean a specific book (for example, belonging to a certain person), we get one option, if we mean all the copies that came out of the printing house (for example, circulation of 100 thousand books) - another option, if keep in mind only those that have survived to the present moment - the third option. Therefore, it is necessary to be precise when specifying sets by enumeration.

But the method of specifying a set using the characteristic properties of elements is fraught with some dangers, since "incorrectly" specified properties can lead to a contradiction. Here is one of the most typical set-theoretic paradoxes - Russell's paradox. Consider the set of all sets that do not contain themselves as an element:

If the set Y exists, then we should be able to answer the following question: YÎY? Let YÎY, then the property defining the set Y must be fulfilled, that is, YÏY. Let YÏY, then, since the property defining Y is satisfied, we come to the fact that YÎY, and this contradicts the assumption. It turns out an unremovable logical contradiction. Here are three ways to avoid this paradox.

1. Restrict the characteristic predicates used by the view

P (x) = xÎA & Q (x),

where A is a known, knowingly existing set (universe). Usually, the notation (xÎA | Q (x)) is used. For Y, the universe is not specified, and therefore Y is not a set;

2. The theory of types. Objects are of type 0, sets are of type 1, sets of sets are of type 2, etc. Y has no type and is not a set;

3. The characteristic property P (x) is given in the form of a computable function (algorithm). The method for calculating the value of the property XÎX is not specified, and therefore Y is not a set.

The last of the listed methods underlies the so-called constructivism - directions in mathematics, within the framework of which only such objects are considered for which procedures (algorithms) for their generation are known. In constructive mathematics, certain concepts and methods of classical mathematics, fraught with possible paradoxes, are excluded from consideration.

1.3 The number of elements in a set

Cardinality is a generalization of the concept of quantity (the number of elements in a set), which makes sense for all sets, including infinite ones.

There are large, there are smaller infinite sets, among them the countable set is the smallest.

In set theory, a countable set is an infinite set, the elements of which can be numbered with natural numbers. More formally: set X is countable if there is a bijection, where denotes the set of all natural numbers. In other words, a countable set is a set equal to the set of natural numbers.

A countable set is the "smallest" infinite set, that is, in any infinite set there is a countable subset.

Properties:

1. Any subset of a countable set is finite or countable;

2. The union of a finite or countable number of countable sets is countable;

3. The direct product of a finite number of countable sets is countable;

4. The set of all finite subsets of a countable set is countable;

5. The set of all subsets of a countable set is continuous and, in particular, is not countable.

An uncountable set is an infinite set that is not countable. Thus, any set is either finite, countable, or uncountable. The set of rational numbers and the set of algebraic numbers are countable, but the set of real numbers is continuous and, therefore, uncountable. Two sets are said to be equally powerful if there is a bijection between them. The existence of a bijection between sets is an equivalence relation, and the cardinality of a set is the corresponding equivalence class.

Properties

· Two finite sets are equal if and only if they consist of the same number of elements. Those. for a finite set, the concept of cardinality coincides with the usual concept of quantity.

For infinite sets, the cardinality of a set may coincide with the cardinality of its own subset, for example

Z (set of integers) = (-3, -2, -1,0,1,2,3 ...);

N (set of natural numbers) = (1,2,3,4,5,6,7 ...);

0.1, -1.2, -2.3, -3 ... as many integers as natural numbers

1,2, 3,4, 5, 6, 7…

· Cantor's theorem guarantees the existence of a more powerful set for any given: The set of all subsets of the set A is more powerful than A, or | 2A | > | A |.

Using the Cantor square, one can also prove the following useful statement: The Cartesian product of an infinite set A with itself is equal to A.

Following Cantor, the cardinality of a set is called the cardinal number and the cardinality of such a set A is denoted by | A | (Kantor himself used the notation). Sometimes there is a designation.

The cardinality of the set of natural numbers is denoted by the symbol ("aleph-zero"). A set is called infinite if its cardinality, therefore, countable sets are the "smallest" of the infinite sets. The following cardinal numbers in ascending order are indicated.

Sets that are equal to the set of all real numbers are said to have the cardinality of the continuum, and the cardinality of such sets is denoted by the symbol c (continuum). The continuum hypothesis states that.

For cardinalities, as in the case of finite sets, there are concepts: equality, more, less. Those. for any sets A and B only one of the three is possible:

1. | A | = | B | or A and B are equal;

2. | A | > | B | or A is more powerful than B, that is, A contains a subset equal to B, but A and B are not equal;

3. | A |< | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

A situation in which A and B are not equal in power and neither of them has a part equal to the other is impossible. This follows from Zermelo's theorem. Otherwise, this would mean the existence of incomparable capacities (which, in principle, is possible if the axiom of choice is not accepted).

The situation in which | A | > | B | and | A |< | B |, невозможна по теореме Кантора - Бернштейна.

Two sets are called equivalent if their elements can be split into pairs so that no element of these sets will be left outside these pairs.

The set of regular positive fractions contains as many elements as natural numbers.

Chapter 2. Operations on Sets

Various operations can be performed on sets, as well as on many other mathematical objects. As a result of operations, new sets are obtained from the original sets.

2.1 Comparison of sets

set element axiomatic affiliation

A set A is contained in a set B (a set B includes a set A) if each element of A is an element of B:

If u, then A is called a proper subset of B. Note that. By definition.

Two sets are said to be equal if they are subsets of each other:

Set Comparison Theorem... For any sets A and B, there is one and only one of the following possibilities: | A | = | B |, | A |<|B|, |A|>| B |.

2.2 Basic set operations

The following are the basic set operations:

· an association:

Intersection:

Difference:

Symmetric difference:

· addition:

The complement operation implies a certain universe (a set U that contains A):

To better understand the meaning of these operations, Euler - Venn diagrams are used, which show the results of operations on geometric shapes as sets of points.

The union of two sets AÈB (Fig. 2.2.1) is the third set, each element of which belongs to at least one of the sets A and B

The intersection of the sets A∩B (Figure 2.2.2) is a set consisting of all those elements that belong simultaneously to all given sets.

The difference of sets A \ B = A - B (Fig. 2.2.3) is a set, each element of which belongs to the set A, but does not belong to the set B.

Symmetric difference ADB (fig. 2.2.4)

The complement to the set A is called the set of all elements that are not included in the set A (Figure 3.2.5)

2.3 Properties of operations on sets

Let the universe be given U . Then for all A, B, CÌ U the following properties are fulfilled (Table 2.3.1):

Properties of operations on sets

To combine (È)	To cross (Ç)
Idempotency
A È A = A	A Ç A = A
Commutativity
A È B = B È A	A Ç B = B Ç A
Associativity
A È (BÈC) = (A È B) ÈC	A Ç (BÇC) = (A Ç B) ÇC
Distributiveness
A È (BÇC) = (A È B) Ç (A È C)	A Ç (BÈC) = (A Ç B) È (A Ç C)
Absorption
(A Ç B) ÈA = A	(A È B) ÇA = A
Zero properties
A ÈÆ = A	A ÇÆ = Æ
Unit properties
A È U = U	A Ç U = U
Involution
= A
De Morgan's laws

Add-on properties

Difference Expression

Expression for symmetric difference

The validity of the listed properties can be verified in various ways. For example, draw Euler diagrams for the left and right sides of the equality and make sure that they coincide, or carry out formal reasoning for each equality. Consider, for example, the first equality: A È A = A. Let's take an arbitrary element X, belonging to the left side of the equality, X Î A È A... By the definition of the union operation È, we have X Î A È X Î A.Anyway X Î A . Taking an arbitrary element from the set on the left side of the equality, we found that it belongs to the set on the right side. Hence, by the definition of the inclusion of sets, we obtain A È A Ì A. Let now X Î A . Then it is obviously true X Î A È X Î A . Hence, by the definition of the union operation, we have X Î A È A... In this way, A Ì A È A... Therefore, by the definition of equality of sets, A È A = A... Similar reasoning is easy to carry out for the remaining equalities.

Let us prove the distributivity property for the union operation on Euler-Venn diagrams (Figure 2.3.1):

A È (BÇC) = (A È B) Ç (A È C)

Chapter 3. Axiomatic set theory

3.1 Naive set theory

In the early twentieth century, Bertrand Russell, while studying naive set theory, came to a paradox (since then known as Russell's paradox). Thus, the failure of naive set theory and the related Cantor program for the standardization of mathematics was demonstrated. Namely, a number of set-theoretic antinomies were discovered: it turned out that when using set-theoretic representations, some statements can be proved together with their negations (and then, according to the rules of classical propositional logic, absolutely any statement can be "proved"!). The antinomies marked the complete failure of Cantor's program.

After the discovery of Russell's antinomy, some mathematicians (for example, L.E. Ya. Brouwer and his school) decided to completely abandon the use of set-theoretic representations. Another part of mathematicians, headed by D. Hilbert, made a number of attempts to substantiate that part of set-theoretic representations, which seemed to them the least responsible for the emergence of antinomies, on the basis of obviously reliable finite mathematics. For this purpose, various axiomatizations of set theory have been developed.

A feature of the axiomatic approach is the rejection of the underlying concept of Cantor's program of the actual existence of sets in some ideal world. In the framework of axiomatic theories, sets “exist” in an exclusively formal way, and their “properties” may substantially depend on the choice of axiomatics. This fact has always been a target for criticism from those mathematicians who did not agree (as Hilbert insisted) to recognize mathematics as a game of symbols devoid of any content. In particular, N. N. Luzin wrote that “the power of the continuum, if only to think of it as a set of points, is a single kind of reality”, the place of which in the series of cardinal numbers cannot depend on whether the continuum hypothesis is recognized as an axiom, or its denial.

Currently, the most widespread axiomatic set theory is ZFC - the Zermelo - Fraenkel theory with the axiom of choice. The question of the consistency of this theory (and even more so - of the existence of a model for it) remains unresolved.

3.2 Axioms of set theory

Now we have all the means to formulate the system of axioms of set theory ZFC, within the framework of which all the methods of reasoning generally accepted in modern mathematics can be stated and none of the known set-theoretic paradoxes passes. This system allows you to build everything mathematical objects based on the empty set. We represent the system of axioms, Zermelo - Fraenkel (ZF).

1. Axiom of existence of an empty set: There is an empty set Æ;

2. Axiom of the existence of a pair: If there are sets a and b, then there is a set (a, b);

3. Sum axiom: If there is a set X, then there is a set ÈX = (a | aÎb for some bÎX);

4. Axiom of infinity: There is a set w = (0, 1,…, n,…), where 0 = Æ, n + 1 = nÈ (n);

5. Axiom of the set of all subsets: If there is a set A, then there is a set:

P (A) = (B | BÍA);

6. Change axiom: If P (x, y) is some condition on the sets x , at such that for any set x there is at most one set at satisfying P (x, y), then for any set a there is a set (b | P (c, b) for some c Î a);

7. Axiom of extensionality:

Two sets that have the same elements are equal, any set is determined by its elements:

8. Axiom of regularity:

Any non-empty set x has an element a Î x for which

It follows from the axiom of regularity that each set is obtained at some step of the "regular process" of forming the set of all subsets, starting with Æ and similar to the construction of natural numbers from the empty set according to the axiom of infinity. This means that any element of any set is a set constructed from an empty set.

Let us show how the ZF axiomatics allows one to define set-theoretic operations.

1. Let us define the set AÈ B, proceeding from the sets A to B. By the axiom of the existence of a pair, the set (A, B) is formed. Using the sum axiom, we obtain the set È (A, B), which by definition coincides with the set AÈB.

2. The intersection A Ç B of the sets A and B is determined by the change axiom using the following property P (x, y): x = y and x Î A. We have the set (b | P (c, b) and c Î B) = (b | c = b and c Î A and c ÎB) = (c | c Î A and c ÎB).

3. Let us show that axioms 5 and 6 imply the existence of the set A2 = ((a, b) | a, bÎA) for any set A. Since (a, b) = ((a), (a, b) ), then A2 ÍP (P (A)). Let the property P (x, y) mean that there are such a, b A such that x = ((a), (a, b)) and y = x. Then the set A2 is equal to (b | P (c, b), cÎ P (P (A))) and by Axiom 6 it exists.

The system of axioms ZFC is formed from ZF by adding one of the following two equivalent axioms, which, on the one hand, are the least "obvious", and on the other, the most meaningful,

1. Axiom of choice.

For any non-empty set A, there exists a mapping j: P (A) \ (Æ) ®A such that j (X) ÎX | for all XÍ A, X¹Æ.

2. The principle of complete ordering. For any non-empty set A, there is a binary relation £ on A for which (A, £) is a well-ordered set.

In the system ZFC, the principle of transfinite induction holds, which is a generalization of the principle of complete induction: if (A, £) is a well-ordered set, P (x) is some property, then the validity of property P (x) on all elements x Î A follows from the fact that that for any z А the satisfiability of the property P on the elements y, where y< z, влечет выполнимость P(z):

Chapter 4. Representation of sets in a computer

The term "presentation" (they also use the term "implementation") in relation to programming means the following. To set a representation of an object (in this case, a set) means to describe in terms of the used programming system the data structure used to store information about the represented object, and the algorithms over the selected data structures that implement the operations inherent in this object. In this paper, it is assumed that common data structures such as arrays, structures (or records), and pointers are available in the programming system being used. Thus, in relation to sets, the definition of a representation implies a description of a method for storing information about the membership of elements in a set and a description of algorithms for calculating the union, intersection, and other introduced operations.

It should be emphasized that, as a rule, one and the same object can be represented in many different ways, and it is impossible to indicate the method that is best for all possible cases. In some cases, it is beneficial to use one view, and in others, another. The choice of presentation depends on a number of factors: the characteristics of the object being represented, the composition and the relative frequency of use of operations in specific task and so on. The ability to choose the most appropriate representation for a given case is the foundation of the art of practical programming. A good programmer is different in that he knows many different ways of presenting and skillfully selects the most suitable one.

4.1 Implementation of operations on subsets of a given universe U

Let the universe U- finite, and the number of elements in it exceeds the capacity of the computer: | U | < n. Элементы универсума нумеруются: U = (u1 ... un). Subset A of the universe U is represented by a code (machine word or bit scale) C, in which

1 if u1 ОА

0 if un ОА

where C [i] is i-th rank C code;

The intersection code of the sets A and B is the bitwise logical product of the code of the set A and the code of the set B. The code for combining the sets A and B is the bitwise logical sum of the code of the set A and the code of the set B. In most computers, there are corresponding machine instructions for these operations. Thus, operations on small sets are performed very efficiently. If the cardinality of the universe exceeds the size of a machine word, but is not very large, then arrays of bit scales are used to represent the sets. In this case, operations on sets are implemented using loops over array elements.

4.2 Generation of all subsets of the universe

In many enumeration algorithms, it is required to sequentially consider all subsets of a given set. In most computers, integers are represented by codes in the binary number system, and the number 2k - 1 is represented by a code containing k ones. Thus, the number 0 is the representation of the empty set Æ, the number 1 is the representation of the subset of the first element, and so on. The following trivial algorithm lists all subsets of an n-element set.

Algorithm for generating all subsets of an n-element set:

Entrance: n³ 0 is the cardinality of the set;

Exit: sequence of codes of subsets i;

for i from 0 to 2n - 1;

yield i ;

end for ;

The algorithm outputs 2n different integers, hence 2n different codes. As the number increases, the number of bits required to represent it increases. The largest (of the generated) number 2n - 1 requires its representation in exactly n digits. Thus, all subsets are generated, and exactly once. The disadvantage of this algorithm is that the order in which subsets are generated has nothing to do with their composition. For example, following the subset with code 0111, the subset with code 1000 will be listed.

4.3 Representation of sets by ordered lists

If the universe is very large (or infinite), and the considered subsets of the universe are not very large, then the representation using bit scales is not efficient in terms of saving memory. In this case, the sets are represented by a record with two fields: informational and a pointer to the next element. The entire list is represented by a pointer to the first element.

elem = record ;

i : info ; (information field);

n : n(pointer to next element);

end record ;

With this representation, the complexity of the operation Î will be O (n), and the complexity of the operations Ì, Ç, È will be O (n × m), where n and m are the cardinalities of the sets participating in the operation.

If the elements in the lists are ordered, for example, in ascending order of the value of the field i, then the complexity of all operations will be O (n). The efficient implementation of operations on sets represented in the form of ordered lists is based on a very general algorithm known as the merge algorithm. A merge-type algorithm looks through two sets in parallel, represented by ordered lists, and at each step the advance occurs in the set in which the current element is smaller.

Conclusion

The course project is carried out on the theme "Elements of set theory". It addresses the following issues:

Sets: elements and sets, methods of specifying sets, the number of elements in a set;

Operations on sets: comparison of sets, basic operations on sets, properties of operations on sets;

Axiomatic set theory: naive set theory, axioms of set theory;

Representation of sets in a computer: Implementation of operations on subsets of a given universe U , Generation of all subsets of the universe; Representation of sets by ordered lists;

Based on the information found (textbooks, Internet), I have identified the main points that most fully and accurately give an idea of set theory. When performing the work, examples of sets were given, as well as those examples that lead to contradictions when different way their assignments. When investigating the properties of operations on sets, I proved one of the properties (distributivity) using Euler-Venn diagrams. And I think that in the last chapter it was necessary to point out the connection between sets and their representation on a computer, this is especially important, in my opinion, for the specialty of a mathematician-programmer.

After the work done, you can do next output:

The concepts of "sets" and "elements of sets" constitute the basic vocabulary of mathematical logic. It is these concepts that lay the foundation that is necessary for further constructions.

List of used literature

1. Discrete mathematics for programmers / FA Novikov. - SPb .: Peter, 2002 .-- 304 p.

2. Zholkov S.Yu. Mathematics and Informatics for Humanities: Textbook. - M .: Gardariki, 2002 .-- 531 p.

3. Sudoplatov S.V., Ovchinnikova E.V. The elements discrete mathematics: Textbook. - M .: INFRA-M, Novosibirsk: Publishing house of NSTU, 2002 .-- 280 p. - (Series " Higher education»)

4. Shipachev V.S. Higher mathematics... Textbook. For universities. - 4th ed., Erased. - M .: graduate School... 1998 .-- 479 p.

5. Material from Wikipedia - the free encyclopedia. Georg Cantor (http://www.peoples.ru/science/mathematics/kantor/)

Test: Fundamentals of Set Theory A set that contains no elements.

Answer:

empty set

A set containing a finite number of elements.

Answer:

finite set

A set that is neither finite nor empty.

Answer:

endless set

Many rivers in Russia.

empty

Lots of people living on Mars.

the final

A set of points on a circle.

endless

set of natural numbers

set of integers

set of rational numbers

set of real numbers

Commutativity

AIB = BIA

Associativity

AИ (B∩C) = (AИB) ∩ (AИC)

Distributiveness

(AИB) ИC = AИ (BIS)

Methods for specifying sets:

enumeration of all elements of the set

using Euler circles

indication of the characteristic property of the elements of the set

specifying the first and last elements of the set

complement to the set

universal set

equal

subset

Set A is a subset of the set D

The set D is a subset of the set A

Set A and set D are equal

Set A - degree of set D

(0;1)

(3;1)

(2;0)

(1;0)

many students of the faculty with a home personal computer

empty set

sets A and B are equal

Let the set M = (- 1; 1) be an interval, and the set N = [- 1; 0] is a segment of the numerical axis, then the set K = M З N, as a numerical interval will be equal to ...

K = [- 1, 1]

K = (- 1.0]

K = (- 1.0)

K = (- 1, 1]

		(-1;0)
		(1;1)
		(0;1)
		(-1;1)

symmetric difference

addition

equal

Choose the correct statements:

Infinite uncountable sets are less powerful than infinite uncountable sets.

Infinite uncountable sets are more powerful than infinite countable sets.

Infinite countable sets are sets that have reached the cardinality of the continuum.

Any finite set will be less powerful than any infinite countable set.

sets A and B consist of the same elements

sets A and B are equal

set A includes set B

set A is a subset of set B

Simplify if A = B, A∩C =∅ :

(((AИB) ∩ (C∩C)) \ (B∩A) ∩B)) ∆A =…

empty set

Simplify if A = B, A∩C =∅ :

((D \ (A∩B)) ∩ ((CIC) ∩B) =…

empty set

Simplify if A = B, A∩C =∅ :

(C∩B) ∆ ((AИB) AND (C∩A)) =…

empty set

X = (1.5); Y = (1,2,4); Z = (2.5)

Find the set: XИ (Y∩Z)

{1,2,4,5}

{1,2,5}

{1,4,5}

{1,2,4}

Let the following sets be given:

X = (1,2,3,4,5); X = (1.5); Y = (1,2,4); Z = (2.5)

Find the set: (XИY) ∩ (XИZ)

{1,2,4,5}

{1,5}

{1,2,5}

{2,5}

A = (5, 7, 9) AND (5,12, 15)

Follow the steps and determine the cardinality of the resulting set:

B = {5, 7, 9, 12} Z{5,12, 15}

Follow the steps and determine the cardinality of the resulting set:

A = (5, 7, 9) З{5, 57, 59}

Follow the steps and determine the cardinality of the resulting set:

B = {5, 7, 9} AND{5, 57, 59}

Follow the steps and determine the cardinality of the resulting set:

{1, 2, 3}\ {2, 3}

Follow the steps and determine the cardinality of the resulting set:

{1, 2, 3}\ {4, 5}

x ≤ 3

x  (1, 2, 3)

1 < x < 5

x  (2, 3, 4)

3 < x ≤ 6

x  (4, 5, 6)

2 ≤ x ≤ 4

1 ≤ x< 4

How many students completed all the problems?

40 students took part in the Mathematics Olympiad for applicants, they were asked to solve one problem in algebra, one in geometry and one in trigonometry. In algebra, 20 people solved the problem, in geometry - 18 people, in trigonometry - 18 people.

7 people decided on algebra and geometry, 9 people decided on algebra and trigonometry. No problem was solved by 3 people.

How many students solved only two problems?

7 people decided on algebra and geometry, 9 people decided on algebra and trigonometry. No problem was solved by 3 people.

How many students solved only one problem?

The first or second test papers in mathematics were successfully written by 33 students, the first or third - 31 students, the second or third - 32 students. At least two tests were completed by 20 students.

How many students have successfully solved only one test?

There are 35 students in the class. Each of them uses at least one of the types of public transport: metro, bus and trolleybus. All three types of transport are used by 6 students, metro and bus - 15 students, metro and trolleybus - 13 students, trolleybus and bus - 9 students.

How many students use only one mode of transportation?

Answer:

Let A = (1,2,3,8) and B = (a, b, c)