Difference between revisions of "Set"
MuchYorick (talk | contribs) |
|||
| Line 9: | Line 9: | ||
== Examples == | == Examples == | ||
| − | There is the set of | + | There is the set of poor children, about which striking conclusions can be drawn. Given the large and diverse number of elements of this set, it would likely include many who could surpass existing athletic and intellectual achievements, if they had access to proper nutrition, health care, and educational institutions. Indeed, many of the world records and [[Nobel Prize]] achievements recognized today would have been outdone by members of this set. |
Another striking example is the how traditional marriage provides a greater set than otherwise: the union of <math>A = \{a, b, c, d\}\,</math> and <math>B = \{a, b, c, e\}\,</math> is merely <math>\{a, b, c, d, e\}\,</math>, while the union of a man, <math>M = \{a, b, c, d\}\,</math> and a woman <math>W = \{e, f, g, h\}\,</math>, is <math>\{a, b, c, d, e, f, g, h\}\,</math>, which is a broader and more diverse set. | Another striking example is the how traditional marriage provides a greater set than otherwise: the union of <math>A = \{a, b, c, d\}\,</math> and <math>B = \{a, b, c, e\}\,</math> is merely <math>\{a, b, c, d, e\}\,</math>, while the union of a man, <math>M = \{a, b, c, d\}\,</math> and a woman <math>W = \{e, f, g, h\}\,</math>, is <math>\{a, b, c, d, e, f, g, h\}\,</math>, which is a broader and more diverse set. | ||
Revision as of 23:56, August 7, 2012
A set is a collection of objects. Sets are the subject of set theory. Two sets are the same if they contain the same elements, regardless of the order they are in. Sets are written in set notation, such as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2\}} indicating the set containing the elements 1 and 2. This is the same as the set because order does not matter when comparing sets.
Also, repetition of elements is irrelevant, so the set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2,2\}} is the same as the set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2\}} .
An important concept in set theory is cardinality. In the case of finite sets, this is simply the number of elements of the set. So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2\}} has a cardinality of 2. However, the theory is more complicated in the case of infinite sets.
It was thought that an informal concept of sets (Naive set theory) was sufficient, however Russell's Paradox shows that this can lead to a contradiction if sets are allowed to contain themselves. Modern set theory is more formal, and disallows such paradoxical sets.
Examples
There is the set of poor children, about which striking conclusions can be drawn. Given the large and diverse number of elements of this set, it would likely include many who could surpass existing athletic and intellectual achievements, if they had access to proper nutrition, health care, and educational institutions. Indeed, many of the world records and Nobel Prize achievements recognized today would have been outdone by members of this set.
Another striking example is the how traditional marriage provides a greater set than otherwise: the union of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \{a, b, c, d\}\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B = \{a, b, c, e\}\,} is merely Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a, b, c, d, e\}\,} , while the union of a man, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M = \{a, b, c, d\}\,} and a woman , is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a, b, c, d, e, f, g, h\}\,} , which is a broader and more diverse set.
Define "A" as the set of all false assertions, and "B" as the set of all the Bible passages. Since there are no Counterexamples to the Bible, the intersection between set A and set B is the empty set. On the other hand, if "C" is set of evolutionary assertions, then the intersection between set A and set C is not empty because it contains Counterexamples to Evolution.
Application -- Combinatorics
Sets, and their cardinalities, are used in some very important aspects of combinatorics, that is, the study of combinations. Let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = \{a,b,c\}\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y = \{p,q,r\}\,} .
The cardinalities of both are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|X\| = \|Y\| = 3} .
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{\{x,y\}\ |\ x \in X \and y \in Y\}}
. The vertical bar means "such that", and the epsilon-like symbol means "is an element of". So this means that S is the collection of sets[1] which are pairs x and y such that x is in X and y is in Y.
We can enumerate this.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{\{a,p\}, \{a,q\}, \{a,r\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}\}\,} .
Its cardinality is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|S\| = 9} .
Now try a harder example, based on the same two sets. Let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \{F\ |\ F \subset (X \cup Y) \and \|F\|=2\}} .
Now Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \cup Y = \{a,b,c,p,q,r\}} , so
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|X \cup Y\| = 6} .
The problem of finding the number of subsets of a set that has some particular cardinality is the combination choosing problem, and shows up in many areas of probability and statistics. In this case, it's the problem of choosing 2 elements out of a set of 6 elements. The number of such choices is often written Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_6C_2\,} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 \choose 2} , and is often pronounced "six choose two". These numbers are also called the binomial coefficients because they appear as coefficients in the expansion of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^n\,} . In this case, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 \choose 2} is the coefficient of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2y^4\,} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^6\,} .
There is a simple formula for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \choose k}
. It is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose k} = \frac{n!}{k! (n-k)!}} .
In the case of the set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \{F\ |\ F \subset \{a,b,c,p,q,r\} \and \|F\|=2\}} , the set is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \{\{a,b\}, \{a,c\}, \{a,p\}, \{a,q\}, \{a,r\}, \{b,c\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}, \{p,q\}, \{p,r\}, \{q,r\}\}\,} .
Its cardinality is 15.
We can check that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {6 \choose 2} = \frac{6!}{2! (6-2)!} = \frac{720}{2 \cdot 24} = 15} .
References
- ↑ Mathematicians don't like to use the phrase "set of sets", since this can lead to some unpleasant paradoxes. So they say "collection of sets." A "collection" is really just a set.