Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Set"

 
(→‎Rough Definition)
 
(45 intermediate revisions by 13 users not shown)
Line 1: Line 1:
−
{{stub}}
+
The notion of a '''set''' is one of the fundamental notions in mathematics that is difficult to precisely define. Of course, we have plenty of synonyms for the word "set," like ''collection, ensemble, group'', etc., but those names really do not define the meaning of the word ''set''; all they can do is replace it in various sentences. So, instead of defining what sets are, one has to define what can be done with them or, in other words, what axioms the sets satisfy. These axioms are chosen to agree with our intuitive concept of a set, on one hand, and to allow various, sometimes quite sophisticated, mathematical constructions on the other hand. For the full collection of these axioms, see [[Zermelo-Fraenkel Axioms]]. In this article we shall present just a brief discussion of the most common properties of sets and operations related to them.
−
==Introduction==
 
  
−
The notion of a set is one of the fundamental notions in mathematics that has to be left undefined. Of course, we have plenty of synonyms for the word set like ''collection, ensemble, group'', etc. but those names really do not define the meaning of the word ''set'': all they can do is to replace it in various sentences. So, instead of defining what sets are, one has to define what can be done with them or, in other words, what axioms the sets satisfy. These axioms are chosen to agree with our intuitive concept of a set on one hand and to allow various, sometimes quite sophisticated, mathematical constructions on the other hand. For the full collection of these axioms, see [[Zermelo-Fraenkel Axioms]]. In this article we shall present just a brief discussion of the most common properties of sets and operations related to them.
+
==Rough Definition==
 +
A set is a collection of objects. The objects can be anything: numbers, letters, libraries that have at least 20 male staff, or absolutely nothing. Order does not matter. What does matter is what is in the set. There might be a [[finite]] number of objects in the set, in which case it is called a finite set. Otherwise we call it an [[infinite]] set. The objects in a set are called the [[element]]s of the set. A common misconception is that a set can have multiple indistinct elements, such as the following: <math>\{1,4,5,3,24,4,4,5,6,2\}</math> Such an entity is actually called a multiset.
  
−
==Relation of ''belonging''==
+
==Relation of ''Belonging''==
 +
The most important property of sets is that, for every ''object'' <math>x</math> and a set <math>S</math>, we can say whether <math>x</math> belongs to <math>S</math> (written as <math>x\in S</math>), or not (written as <math>x\notin S</math>). Two sets <math>S'</math> and <math>S''</math> are equal if they include the same objects, i.e., if for every object <math>x</math>, we have <math>x\in S'</math> if and only if <math>x\in S''</math>. 
  
−
The most important property of sets is that, for every ''object'' <math>x</math> and a set <math>S</math>, we can say whether <math>x</math> belongs to <math>S</math> (written as <math>x\in S</math>) or not (written as <math>x\notin S</math>). Two sets <math>S'</math> and <math>S''</math> are equal if they include the same objects, i.e., if for every object <math>x</math>, we have <math>x\in S'</math> if and only if <math>x\in S''</math>.
+
==Specifying a Set==
 +
There are many ways to specify a set, using different notation.
  
−
==Specifying a set by listing its objects==
+
===Listing its Elements===
 +
This means that in order to identify a particular set, it suffices to tell which objects belong to this set. If the set contains just several such objects, all you need to do is list them. So, you can specify the set consisting of the numbers <math>1,3,5</math>, and <math>239</math>, for example. (The standard notation for this set is <math>\{1,3,5,239\}</math>. Note that the order in which the terms are listed is completely unimportant: we have to follow some order when writing things in one line, but you should actually imagine those numbers flowing freely inside those curly braces with no preference given to any of them. What matters is that these four numbers are in the set and everything else is out).  But how do you specify sets that have very many (maybe [[infinite]]ly many) elements? You cannot list them all even if you spend your entire life writing!
  
−
It means that in order to determine the set, it suffices to tell which objects belong to this set. If you have just several such objects, all you need to do is to list them. So, you can specify the set consisting of the numbers <math>1,3,5</math>, and <math>239</math>, for example. (The standard notation for this set is <math>\{1,3,5,239\}</math>. note that the order in which the terms are listed is completely unimportant: we have to follow some order when writing things in one line but you should actually imagine those numbers flowing freely inside those curly braces with no preference given to any of them. What matters is that these four numbers are in the set and everything else is out).
+
===Stating the Common Property of its Elements===
−
But how do you specify sets that have very many (maybe [[infinite]]ly many) elements? You cannon list them all even if you spend your entire life writing!
+
Another way to specify a set is to use some property to tell when an object belongs to this set. For instance, we may try to think (alas, only try!) of the set of all objects with green hair. In this case, we do not even try to list all such objects. We just decide that something belongs to this set if it has green hair and doesn't belong to it otherwise. This is a wonderful way to describe a set.  
  
−
==Specifying a set by the common property of its elements==
+
Unfortunately, this method has several potential pitfalls.  It turns out, counter-intuitively, that not every collection of objects with a certain property is a set.  The most famous example of this problem is [[Russell's Paradox]]: consider the property, "is a set and does not contain itself."  (Remember that, given a set, we should be able to tell about '''every''' object whether it belongs to this set or not; in particular, we can ask this question about the set itself).  The set <math>S</math> specified by this property can neither belong, nor not belong to itself.  There are a variety of ways to resolve this paradox, but the problem is clear: this way to describe sets should be used with extreme caution.  One way to avoid this problem is as follows: given a property <math>P</math>, choose a known set <math>T</math>.  Then the collection <math>S</math> of elements of <math>T</math> which have property <math>P</math> will always be a set.  (In particular, for our previous example to lead to a paradox, we would need to choose <math>T = \{\mathrm{all \; sets}\}</math>.  However, it turns out that it can be proven that the set of all sets does not exist -- the collection of all sets is too big to be a set.)
  
−
Another way to specify a set is to use some property to tell when an object belongs to this set. For instance, we may try to think (alas, only try!) of the set of all objects with green hair. In this case we do not even try to list all such objects. We just decide that something belongs to this set if it has green hair and doesn't belong to it otherwise. This is a wonderful way to describe a set. Unfortunately, it just doesn't work that simply. Indeed, consider the property that an object is a set that does not belong to itself (remember, that, given a set, we should be able to tell about '''every''' object whether it belongs to this set or not; in particular, we can ask this question about the set itself). It is easy to see that the set <math>S</math> specified by this property can neither belong, nor not belong to itself and our whole theory gets self-contradictory. So, this way to describe sets should be used with extreme caution. The way out is that such a description is allowed only in much weaker form: given a set <math>S</math> and a property <math>P</math>, we can define a new set <math>S'</math> of objects in the set <math>S</math> that satisfy the property <math>P</math>.
+
===Set Notation===
 +
There is a notation used just for sets:
 +
 
 +
<math>\{ x \in \mathbb {R} \mid x^2>0 \}</math>
 +
 
 +
That symbolizes the set of all reals not equal to 0. This is probably the fastest way of describing a large set.
 +
 
 +
Also, the empty set can be specified using set notation:
 +
 
 +
<math>\{ x \in \mathbb {R} \mid x^2<0 \}</math>
 +
 
 +
Since there are no reals such that the square of it is less than 0, that set is the empty set.
  
 
==Subsets==
 
==Subsets==
 +
We say that a set <math>A</math> is a [[subset]] of a set <math>S</math> if every object <math>x</math> that belongs to <math>A</math> also belongs to <math>S</math>. This is denoted <math>A\subseteq S</math> or <math>A\subset S</math>. For example, the sets <math>\{1,2\}</math> and <math>\{2,3\}</math> are subsets of the set <math>\{1,2,3\}</math>, but the set <math>\{1,6\}</math> is not.  Thus we can say that two sets are equal if and only if each is a subset of the other. A special kind of subset is the [[empty set]].
 +
 +
==Power Sets==
 +
{{main|power set}}
 +
The [[power set]] of a set <math>A</math>, denoted <math>\mathcal{P}(A)</math> is defined as the set of all its subsets. For example, the power set of <math>\{1,2,3\}</math> is <math>\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}</math>. If a <math>A</math> is a [[finite]] set of size <math>n</math> then <math>\mathcal{P}(A)</math> has size <math>2^n</math>.
 +
 +
== Operations==
 +
===Union and Intersection===
 +
The [[union]] of two or more sets is the set of all objects that belong to one or more of the sets. The union of A and B is denoted <math>A\cup B</math>. For example, the union of <math>\{1,2\}</math> and <math>\{1,3,5\}</math> is <math>\{1,2,3,5\}</math>. Unions can also be represented just as sums and products can be. <math>\bigcup_{statement}S</math> would be the union of all sets <math>S</math> that satisfy the statement. So, for example, <math>\bigcup_{S\subset\mathbb{N}}S</math> would be the set of all natural numbers <math>\mathbb{N}</math>.
 +
 +
The [[intersection]] of two or more sets is the set of all objects that belong to all of the sets. The intersection of A and B is denoted <math>A\cap B</math>. For example, the intersection of <math>\{1,2\}</math> and <math>\{1,3,5\}</math> is <math>\{1\}</math>. Just like unions, intersections can be represented as such: <math>\bigcap_{statement}S</math>. For example, <math>\bigcap_{S\,is\,P(A)\,for\,some\,set\,A}S=\emptyset</math>, or the empty set defined next. 
 +
 +
===Cartesian Product===
 +
The '''Cartesian Product''' of two sets <math>A</math> and <math>B</math> is defined as the set of [[Ordered Pair]]s <math>(a,b)</math> such that <math>a\in A</math> and <math>b\in B</math>
 +
<math>A\times B=\{(a,b)|a\in A, b\in B\}</math>
 +
 +
==Empty Set==
 +
{{main|empty set}}
 +
An [[empty set]], denoted <math>\emptyset</math> is a set with no elements.
 +
 +
An empty set has some special properties:
 +
 +
*It is a subset of every other set.
 +
*The union of any other set and an empty set is the original set.
 +
*The intersection of any other set and an empty set is an empty set.
 +
 +
==Infinite Sets==
 +
An [[infinite]] set can be defined as a set that has the same [[cardinality]] as one of its proper subsets.  Alternatively, infinite sets are those which cannot be put into [[correspondence]] with any set of the form <math>\{1, 2, ..., n\}</math>.
 +
 +
== Cardinality==
 +
The [[cardinality]] of a set <math>A</math>, denoted <math>|A|</math>, is (informally) the size of the set.  For a finite set, the cardinality is simply the number of elements.  The empty set has cardinality 0. 
 +
 +
<math>|A|=|B|</math> [[iff]] there is a bijective function <math>f:A\to B</math> meaning that there is a function <math>f</math> that maps all elements of <math>A</math> to all the elements of <math>B</math> with one-to-one correspondence. 
 +
 +
<math>|A|\le|B|</math> iff there exists an injective function <math>f:A\to B</math> meaning there is a function <math>f</math> that maps all elements of <math>A</math> to (not necessarily all) elements of <math>B</math>. <math>|A|\ge|B|</math> can be defined similarily by expressing it as <math>|B|\le|A|</math>.
 +
 +
<math>|A|<|B|</math> iff there exists an injective function <math>f:A\to B</math> and there is no bijective function <math>g:A\to B</math> meaning <math>|A|\le|B|</math> but <math>|A|\neq|B|</math>. <math>|A|>|B|</math> is defined similarly.
  
−
==Power set==
+
Although showing that <math>A\le B</math> and <math>B\le A</math> implies that <math>A=B</math> is easy to prove when using finite sets, it is more complicated when using infinite sets. This theorem is called the [[Cantor-Bernstein-Schröder theorem]] and was proven by [[Georg Cantor]], [[Felix Bernstein]], and [[Ernst Schröder]].
  
−
==Union and intersection==
+
==Problems==
 +
===Introductory===
 +
*The regular 5-point star <math>ABCDE</math> is drawn and in each [[vertex]], there is a number. Each <math>A,B,C,D,</math> and <math>E</math> are chosen such that all 5 of them came from set <math>\{3,5,6,7,9\}</math>. Each letter is a different number (so one possible way is <math>A = 3, B = 5, C = 6, D = 7, E = 9</math>). Let <math>AB</math> be the sum of the numbers on <math>A</math> and <math>B</math>, and so forth. If <math>AB, BC, CD, DE,</math> and <math>EA</math> form an [[arithmetic sequence]] (not necessarily in increasing order), find the value of <math>CD</math>.
  
−
==Empty set==
+
<math>
 +
(\mathrm {A}) \ 9 \qquad (\mathrm {B}) \ 10 \qquad (\mathrm {C})\ 11 \qquad (\mathrm {D}) \ 12 \qquad (\mathrm {E})\ 13
 +
</math>
 +
([[2005 AMC 12A Problems/Problem 13|Source]])
 +
===Intermediate===
 +
*Let [[set]] <math> \mathcal{A} </math> be a 90-[[element]] [[subset]] of <math> \{1,2,3,\ldots,100\}, </math> and let <math> S </math> be the sum of the elements of <math> \mathcal{A}. </math> Find the number of possible values of <math> S. </math>
 +
([[2006 AIME I Problems/Problem 2|Source]])
 +
===Olympiad===
 +
*Let <math> r \ge 2 </math> be a fixed positive integer, and let <math>F </math> be an infinite family of sets, each of size <math>r </math>, no two of which are disjoint.  Prove that there exists a set of size <math>r-1 </math> that meets each set in <math>F </math>.
 +
([[2002 IMO Shortlist Problems/C5|Source]])
 +
==See Also==
 +
*[[Set theory]]
 +
*[[Function]]
  
−
==Infinite sets==
+
==External Links==
 +
*[http://books.google.com/books?id=x6cZBQ9qtgoC&dq=sets&pg=PP1&ots=EeaGUypaDZ&source=citation&sig=VvPWFTxvdC3UTOqC0rR4waZlbOI&hl=en&prev=http://www.google.com/search?q=sets&ie=utf-8&oe=utf-8&rls=org.mozilla:en-US:official&client=firefox-a&sa=X&oi=print&ct=result&cd=1&cad=bottom-3results Naive Set Theory] by Paul R. Halmos.
 +
*[http://books.google.com/books?id=3-nrPB7BQKMC&dq=sets&pg=PP1&ots=0k1yGKTYC9&source=citation&sig=G28XMjBVX9_taS-_XQOTdf20BnA&hl=en&prev=http://www.google.com/search?q=sets&ie=utf-8&oe=utf-8&rls=org.mozilla:en-US:official&client=firefox-a&sa=X&oi=print&ct=result&cd=2&cad=bottom-3results Set Theory and Logic] by Robert Roth Stoll.
  
−
''To be continued''
+
[[Category:Definition]]
 +
[[Category:Set theory]]

Latest revision as of 16:20, 7 July 2024

The notion of a set is one of the fundamental notions in mathematics that is difficult to precisely define. Of course, we have plenty of synonyms for the word "set," like collection, ensemble, group, etc., but those names really do not define the meaning of the word set; all they can do is replace it in various sentences. So, instead of defining what sets are, one has to define what can be done with them or, in other words, what axioms the sets satisfy. These axioms are chosen to agree with our intuitive concept of a set, on one hand, and to allow various, sometimes quite sophisticated, mathematical constructions on the other hand. For the full collection of these axioms, see Zermelo-Fraenkel Axioms. In this article we shall present just a brief discussion of the most common properties of sets and operations related to them.

Rough Definition

A set is a collection of objects. The objects can be anything: numbers, letters, libraries that have at least 20 male staff, or absolutely nothing. Order does not matter. What does matter is what is in the set. There might be a finite number of objects in the set, in which case it is called a finite set. Otherwise we call it an infinite set. The objects in a set are called the elements of the set. A common misconception is that a set can have multiple indistinct elements, such as the following: $\{1,4,5,3,24,4,4,5,6,2\}$ Such an entity is actually called a multiset.

Relation of Belonging

The most important property of sets is that, for every object $x$ and a set $S$, we can say whether $x$ belongs to $S$ (written as $x\in S$), or not (written as $x\notin S$). Two sets $S'$ and $S''$ are equal if they include the same objects, i.e., if for every object $x$, we have $x\in S'$ if and only if $x\in S''$.

Specifying a Set

There are many ways to specify a set, using different notation.

Listing its Elements

This means that in order to identify a particular set, it suffices to tell which objects belong to this set. If the set contains just several such objects, all you need to do is list them. So, you can specify the set consisting of the numbers $1,3,5$, and $239$, for example. (The standard notation for this set is $\{1,3,5,239\}$. Note that the order in which the terms are listed is completely unimportant: we have to follow some order when writing things in one line, but you should actually imagine those numbers flowing freely inside those curly braces with no preference given to any of them. What matters is that these four numbers are in the set and everything else is out). But how do you specify sets that have very many (maybe infinitely many) elements? You cannot list them all even if you spend your entire life writing!

Stating the Common Property of its Elements

Another way to specify a set is to use some property to tell when an object belongs to this set. For instance, we may try to think (alas, only try!) of the set of all objects with green hair. In this case, we do not even try to list all such objects. We just decide that something belongs to this set if it has green hair and doesn't belong to it otherwise. This is a wonderful way to describe a set.

Unfortunately, this method has several potential pitfalls. It turns out, counter-intuitively, that not every collection of objects with a certain property is a set. The most famous example of this problem is Russell's Paradox: consider the property, "is a set and does not contain itself." (Remember that, given a set, we should be able to tell about every object whether it belongs to this set or not; in particular, we can ask this question about the set itself). The set $S$ specified by this property can neither belong, nor not belong to itself. There are a variety of ways to resolve this paradox, but the problem is clear: this way to describe sets should be used with extreme caution. One way to avoid this problem is as follows: given a property $P$, choose a known set $T$. Then the collection $S$ of elements of $T$ which have property $P$ will always be a set. (In particular, for our previous example to lead to a paradox, we would need to choose $T = \{\mathrm{all \; sets}\}$. However, it turns out that it can be proven that the set of all sets does not exist -- the collection of all sets is too big to be a set.)

Set Notation

There is a notation used just for sets:

$\{ x \in \mathbb {R} \mid x^2>0 \}$

That symbolizes the set of all reals not equal to 0. This is probably the fastest way of describing a large set.

Also, the empty set can be specified using set notation:

$\{ x \in \mathbb {R} \mid x^2<0 \}$

Since there are no reals such that the square of it is less than 0, that set is the empty set.

Subsets

We say that a set $A$ is a subset of a set $S$ if every object $x$ that belongs to $A$ also belongs to $S$. This is denoted $A\subseteq S$ or $A\subset S$. For example, the sets $\{1,2\}$ and $\{2,3\}$ are subsets of the set $\{1,2,3\}$, but the set $\{1,6\}$ is not. Thus we can say that two sets are equal if and only if each is a subset of the other. A special kind of subset is the empty set.

Power Sets

Main article: power set

The power set of a set $A$, denoted $\mathcal{P}(A)$ is defined as the set of all its subsets. For example, the power set of $\{1,2,3\}$ is $\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$. If a $A$ is a finite set of size $n$ then $\mathcal{P}(A)$ has size $2^n$.

Operations

Union and Intersection

The union of two or more sets is the set of all objects that belong to one or more of the sets. The union of A and B is denoted $A\cup B$. For example, the union of $\{1,2\}$ and $\{1,3,5\}$ is $\{1,2,3,5\}$. Unions can also be represented just as sums and products can be. $\bigcup_{statement}S$ would be the union of all sets $S$ that satisfy the statement. So, for example, $\bigcup_{S\subset\mathbb{N}}S$ would be the set of all natural numbers $\mathbb{N}$.

The intersection of two or more sets is the set of all objects that belong to all of the sets. The intersection of A and B is denoted $A\cap B$. For example, the intersection of $\{1,2\}$ and $\{1,3,5\}$ is $\{1\}$. Just like unions, intersections can be represented as such: $\bigcap_{statement}S$. For example, $\bigcap_{S\,is\,P(A)\,for\,some\,set\,A}S=\emptyset$, or the empty set defined next.

Cartesian Product

The Cartesian Product of two sets $A$ and $B$ is defined as the set of Ordered Pairs $(a,b)$ such that $a\in A$ and $b\in B$ $A\times B=\{(a,b)|a\in A, b\in B\}$

Empty Set

Main article: empty set

An empty set, denoted $\emptyset$ is a set with no elements.

An empty set has some special properties:

  • It is a subset of every other set.
  • The union of any other set and an empty set is the original set.
  • The intersection of any other set and an empty set is an empty set.

Infinite Sets

An infinite set can be defined as a set that has the same cardinality as one of its proper subsets. Alternatively, infinite sets are those which cannot be put into correspondence with any set of the form $\{1, 2, ..., n\}$.

Cardinality

The cardinality of a set $A$, denoted $|A|$, is (informally) the size of the set. For a finite set, the cardinality is simply the number of elements. The empty set has cardinality 0.

$|A|=|B|$ iff there is a bijective function $f:A\to B$ meaning that there is a function $f$ that maps all elements of $A$ to all the elements of $B$ with one-to-one correspondence.

$|A|\le|B|$ iff there exists an injective function $f:A\to B$ meaning there is a function $f$ that maps all elements of $A$ to (not necessarily all) elements of $B$. $|A|\ge|B|$ can be defined similarily by expressing it as $|B|\le|A|$.

$|A|<|B|$ iff there exists an injective function $f:A\to B$ and there is no bijective function $g:A\to B$ meaning $|A|\le|B|$ but $|A|\neq|B|$. $|A|>|B|$ is defined similarly.

Although showing that $A\le B$ and $B\le A$ implies that $A=B$ is easy to prove when using finite sets, it is more complicated when using infinite sets. This theorem is called the Cantor-Bernstein-Schröder theorem and was proven by Georg Cantor, Felix Bernstein, and Ernst Schröder.

Problems

Introductory

  • The regular 5-point star $ABCDE$ is drawn and in each vertex, there is a number. Each $A,B,C,D,$ and $E$ are chosen such that all 5 of them came from set $\{3,5,6,7,9\}$. Each letter is a different number (so one possible way is $A = 3, B = 5, C = 6, D = 7, E = 9$). Let $AB$ be the sum of the numbers on $A$ and $B$, and so forth. If $AB, BC, CD, DE,$ and $EA$ form an arithmetic sequence (not necessarily in increasing order), find the value of $CD$.

$(\mathrm {A}) \ 9 \qquad (\mathrm {B}) \ 10 \qquad (\mathrm {C})\ 11 \qquad (\mathrm {D}) \ 12 \qquad (\mathrm {E})\ 13$ (Source)

Intermediate

  • Let set $\mathcal{A}$ be a 90-element subset of $\{1,2,3,\ldots,100\},$ and let $S$ be the sum of the elements of $\mathcal{A}.$ Find the number of possible values of $S.$

(Source)

Olympiad

  • Let $r \ge 2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$, no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$.

(Source)

See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Set&oldid=221846"