From ef0480286342219c7a592926660018534f5af12a Mon Sep 17 00:00:00 2001 From: a'_ <43641740+A-ee@users.noreply.github.com> Date: Fri, 10 Apr 2020 11:16:05 +0800 Subject: Propose Set Theory --- set-theory.html.markdown | 143 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 143 insertions(+) create mode 100644 set-theory.html.markdown (limited to 'set-theory.html.markdown') diff --git a/set-theory.html.markdown b/set-theory.html.markdown new file mode 100644 index 00000000..988c4397 --- /dev/null +++ b/set-theory.html.markdown @@ -0,0 +1,143 @@ +--- +category: Algorithms & Data Structures +name: Set theory +contributors: +--- +The set theory is a study for sets, their operations, and their properties. It is the basis of the whole mathematical system. + +* A set is a collection of definite distinct items. + +## Basic operators +These operators don't require a lot of text to describe. + +* `∨` means or. +* `∧` means and. +* `,` separates the filters that determine the items in the set. + +## A brief history of the set theory +### Naive set theory +* Cantor invented the naive set theory. +* It has lots of paradoxes and initiated the third mathematical crisis. + +### Axiomatic set theory +* It uses axioms to define the set theory. +* It prevents paradoxes from happening. + +## Built-in sets +* `∅`, the set of no items. +* `N`, the set of all natural numbers. `{0,1,2,3,…}` +* `Z`, the set of all integers. `{…,-2,-1,0,1,2,…}` +* `Q`, the set of all rational numbers. +* `R`, the set of all real numbers. +### The empty set +* The set containing no items is called the empty set. Representation: `∅` +* The empty set can be described as `∅ = {x|x ≠ x}` +* The empty set is always unique. +* The empty set is the subset of all sets. +``` +A = {x|x∈N,x < 0} +A = ∅ +∅ = {} (Sometimes) + +|∅| = 0 +|{∅}| = 1 +``` +## Representing sets +### Enumeration +* List all items of the set, e.g. `A = {a,b,c,d}` +* List some of the items of the set. Ignored items are represented with `…`. E.g. `B = {2,4,6,8,10,…}` + +### Description +* Describes the features of all items in the set. Syntax: `{body|condtion}` +``` +A = {x|x is a vowel} +B = {x|x ∈ N, x < 10l} +C = {x|x = 2k, k ∈ N} +C = {2x|x ∈ N} +``` + +## Relations between sets +### Belongs to +* If the value `a` is one of the items of the set `A`, `a` belongs to `A`. Representation: `a∈A` +* If the value `a` is not one of the items of the set `A`, `a` does not belong to `A`. Representation: `a∉A` + +### Equals +* If all items in a set are exactly the same to another set, they are equal. Representation: `a=b` +* Items in a set are not order sensitive. `{1,2,3,4}={2,3,1,4}` +* Items in a set are unique. `{1,2,2,3,4,3,4,2}={1,2,3,4}` +* Two sets are equal if and only if all of their items are exactly equal to each other. Representation: `A=B`. Otherwise, they are not equal. Representation: `A≠B`. +* `A=B` if `A ⊆ B` and `B ⊆ A` + +### Belongs to +* If the set A contains an item `x`, `x` belongs to A (`x∈A`). +* Otherwise, `x` does not belong to A (`x∉A`). + +### Subsets +* If all items in a set `B` are items of set `A`, we say that `B` is a subset of `A` (`B⊆A`). +* If B is not a subset of A, the representation is `B⊈A`. + +### Proper subsets +* If `B ⊆ A` and `B ≠ A`, B is a proper subset of A (`B ⊂ A`). Otherwise, B is not a proper subset of A (`B ⊄ A`). + +## Set operations +### Base number +* The number of items in a set is called the base number of that set. Representation: `|A|` +* If the base number of the set is finite, this set is a finite set. +* If the base number of the set is infinite, this set is an infinite set. +``` +A = {A,B,C} +|A| = 3 +B = {a,{b,c}} +|B| = 2 +|∅| = 0 (it has no items) +``` + +### Powerset +* Let `A` be any set. The set that contains all possible subsets of `A` is called a powerset (written as `P(A)`). +``` +P(A) = {x|x ⊆ A} + +|A| = N, |P(A)| = 2^N +``` + +## Set operations among two sets +### Union +Given two sets `A` and `B`, the union of the two sets are the items that appear in either `A` or `B`, written as `A ∪ B`. +``` +A ∪ B = {x|x∈A∨x∈B} +``` +### Intersection +Given two sets `A` and `B`, the intersection of the two sets are the items that appear in both `A` and `B`, written as `A ∩ B`. +``` +A ∩ B = {x|x∈A,x∈B} +``` +### Difference +Given two sets `A` and `B`, the set difference of `A` with `B` is every item in `A` that does not belong to `B`. +``` +A \ B = {x|x∈A,x∉B} +``` +### Symmetrical difference +Given two sets `A` and `B`, the symmetrical difference is all items among `A` and `B` that doesn't appear in their intersections. +``` +A △ B = {x|(x∈A∧x∉B)∨(x∈B∧x∉A)} + +A △ B = (A \ B) ∪ (B \ A) +``` +### Cartesian product +Given two sets `A` and `B`, the cartesian product between `A` and `B` consists of a set containing all combinations of items of `A` and `B`. +``` +A × B = { {x, y} | x ∈ A, y ∈ B } +``` +## "Generalized" operations +### General union +Better known as "flattening" of a set of sets. +``` +∪A = {x|X∈A,x∈X} +∪A={a,b,c,d,e,f} +∪B={a} +∪C=a∪{c,d} +``` +### General intersection +``` +∩ A = A1 ∩ A2 ∩ … ∩ An +``` -- cgit v1.2.3 From 081cf637cc730b04a3c24fa7c630e5b030b614c4 Mon Sep 17 00:00:00 2001 From: Ben Levy <7348004+io12@users.noreply.github.com> Date: Sat, 4 Jul 2020 22:46:46 -0400 Subject: Fix set theory formatting issues --- set-theory.html.markdown | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'set-theory.html.markdown') diff --git a/set-theory.html.markdown b/set-theory.html.markdown index 988c4397..c6bc39c5 100644 --- a/set-theory.html.markdown +++ b/set-theory.html.markdown @@ -29,11 +29,13 @@ These operators don't require a lot of text to describe. * `Z`, the set of all integers. `{…,-2,-1,0,1,2,…}` * `Q`, the set of all rational numbers. * `R`, the set of all real numbers. + ### The empty set * The set containing no items is called the empty set. Representation: `∅` * The empty set can be described as `∅ = {x|x ≠ x}` * The empty set is always unique. * The empty set is the subset of all sets. + ``` A = {x|x∈N,x < 0} A = ∅ @@ -42,6 +44,7 @@ A = ∅ |∅| = 0 |{∅}| = 1 ``` + ## Representing sets ### Enumeration * List all items of the set, e.g. `A = {a,b,c,d}` @@ -49,6 +52,7 @@ A = ∅ ### Description * Describes the features of all items in the set. Syntax: `{body|condtion}` + ``` A = {x|x is a vowel} B = {x|x ∈ N, x < 10l} @@ -84,6 +88,7 @@ C = {2x|x ∈ N} * The number of items in a set is called the base number of that set. Representation: `|A|` * If the base number of the set is finite, this set is a finite set. * If the base number of the set is infinite, this set is an infinite set. + ``` A = {A,B,C} |A| = 3 @@ -94,6 +99,7 @@ B = {a,{b,c}} ### Powerset * Let `A` be any set. The set that contains all possible subsets of `A` is called a powerset (written as `P(A)`). + ``` P(A) = {x|x ⊆ A} @@ -103,41 +109,54 @@ P(A) = {x|x ⊆ A} ## Set operations among two sets ### Union Given two sets `A` and `B`, the union of the two sets are the items that appear in either `A` or `B`, written as `A ∪ B`. + ``` A ∪ B = {x|x∈A∨x∈B} ``` + ### Intersection Given two sets `A` and `B`, the intersection of the two sets are the items that appear in both `A` and `B`, written as `A ∩ B`. + ``` A ∩ B = {x|x∈A,x∈B} ``` + ### Difference Given two sets `A` and `B`, the set difference of `A` with `B` is every item in `A` that does not belong to `B`. + ``` A \ B = {x|x∈A,x∉B} ``` + ### Symmetrical difference Given two sets `A` and `B`, the symmetrical difference is all items among `A` and `B` that doesn't appear in their intersections. + ``` A △ B = {x|(x∈A∧x∉B)∨(x∈B∧x∉A)} A △ B = (A \ B) ∪ (B \ A) ``` + ### Cartesian product Given two sets `A` and `B`, the cartesian product between `A` and `B` consists of a set containing all combinations of items of `A` and `B`. + ``` A × B = { {x, y} | x ∈ A, y ∈ B } ``` + ## "Generalized" operations ### General union Better known as "flattening" of a set of sets. + ``` ∪A = {x|X∈A,x∈X} ∪A={a,b,c,d,e,f} ∪B={a} ∪C=a∪{c,d} ``` + ### General intersection + ``` ∩ A = A1 ∩ A2 ∩ … ∩ An ``` -- cgit v1.2.3 From e9ec0ab695d2aecdaab8639df5395e3ecefc02ce Mon Sep 17 00:00:00 2001 From: bermudalocket Date: Thu, 16 Jul 2020 13:38:08 -0400 Subject: Update set-theory.html.markdown This pull request attempts to fix major inconsistencies and some incorrect information. It also streamlines the article by rearranging and/or removing stubs of information. - Replaced `v` and `^` set operators with cup and cap, respectively; - Removed history section as the information was not necessarily accurate; - Expanded symbols section by splitting it into operators and qualifiers; - Renamed "builtin sets" to "canonical sets"; - Replaced Latin alphabet symbols for canonical sets with their Blackboard bold variants (see: https://en.wikipedia.org/wiki/Blackboard_bold); - Rewrote set relations section to streamline information; - Rewrote examples in set operations section to make meaning more clear; - Removed generalized operations section, as the original author was clearly trying to typeset unions and intersections of collections of sets, but the notation is impossible to replicate in markdown and only makes the section more unclear. --- set-theory.html.markdown | 166 +++++++++++++++++++---------------------------- 1 file changed, 68 insertions(+), 98 deletions(-) (limited to 'set-theory.html.markdown') diff --git a/set-theory.html.markdown b/set-theory.html.markdown index c6bc39c5..6fb657ed 100644 --- a/set-theory.html.markdown +++ b/set-theory.html.markdown @@ -3,107 +3,94 @@ category: Algorithms & Data Structures name: Set theory contributors: --- -The set theory is a study for sets, their operations, and their properties. It is the basis of the whole mathematical system. +Set theory is a branch of mathematics that studies sets, their operations, and their properties. -* A set is a collection of definite distinct items. +* A set is a collection of disjoint items. -## Basic operators -These operators don't require a lot of text to describe. +## Basic symbols -* `∨` means or. -* `∧` means and. -* `,` separates the filters that determine the items in the set. +### Operators +* the union operator, `∪`, pronounced "cup", means "or"; +* the intersection operator, `∩`, pronounced "cap", means "and"; +* the exclusion operator, `\`, means "without"; +* the compliment operator, `'`, means "the inverse of"; +* the cross operator, `×`, means "the Cartesian product of". -## A brief history of the set theory -### Naive set theory -* Cantor invented the naive set theory. -* It has lots of paradoxes and initiated the third mathematical crisis. +### Qualifiers +* the colon qualifier, `:`, means "such that"; +* the membership qualifier, `∈`, means "belongs to"; +* the subset qualifier, `⊆`, means "is a subset of"; +* the proper subset qualifier, `⊂`, means "is a subset of but is not equal to". -### Axiomatic set theory -* It uses axioms to define the set theory. -* It prevents paradoxes from happening. +### Canonical sets +* `∅`, the empty set, i.e. the set containing no items; +* `ℕ`, the set of all natural numbers; +* `ℤ`, the set of all integers; +* `ℚ`, the set of all rational numbers; +* `ℝ`, the set of all real numbers. -## Built-in sets -* `∅`, the set of no items. -* `N`, the set of all natural numbers. `{0,1,2,3,…}` -* `Z`, the set of all integers. `{…,-2,-1,0,1,2,…}` -* `Q`, the set of all rational numbers. -* `R`, the set of all real numbers. +There are a few caveats to mention regarding the canonical sets: +1. Even though the empty set contains no items, the empty set is a subset of itself (and indeed every other set); +2. Mathematicians generally do not universally agree on whether zero is a natural number, and textbooks will typically explicitly state whether or not the author considers zero to be a natural number. -### The empty set -* The set containing no items is called the empty set. Representation: `∅` -* The empty set can be described as `∅ = {x|x ≠ x}` -* The empty set is always unique. -* The empty set is the subset of all sets. -``` -A = {x|x∈N,x < 0} -A = ∅ -∅ = {} (Sometimes) +### Cardinality -|∅| = 0 -|{∅}| = 1 -``` +The cardinality, or size, of a set is determined by the number of items in the set. The cardinality operator is given by a double pipe, `|...|`. + +For example, if `S = { 1, 2, 4 }`, then `|S| = 3`. + +### The Empty Set +* The empty set can be constructed in set builder notation using impossible conditions, e.g. `∅ = { x : x =/= x }`, or `∅ = { x : x ∈ N, x < 0 }`; +* the empty set is always unique (i.e. there is one and only one empty set); +* the empty set is a subset of all sets; +* the cardinality of the empty set is 1, i.e. `|∅| = 1`. ## Representing sets -### Enumeration -* List all items of the set, e.g. `A = {a,b,c,d}` -* List some of the items of the set. Ignored items are represented with `…`. E.g. `B = {2,4,6,8,10,…}` -### Description -* Describes the features of all items in the set. Syntax: `{body|condtion}` +### Literal Sets + +A set can be constructed literally by supplying a complete list of objects contained in the set. For example, `S = { a, b, c, d }`. + +Long lists may be shortened with ellipses as long as the context is clear. For example, `E = { 2, 4, 6, 8, ... }` is clearly the set of all even numbers, containing an infinite number of objects, even though we've only explicitly written four of them. + +### Set Builder + +Set builder notation is a more descriptive way of constructing a set. It relies on a _subject_ and a _predicate_ such that `S = { subject : predicate }`. For example, ``` -A = {x|x is a vowel} -B = {x|x ∈ N, x < 10l} -C = {x|x = 2k, k ∈ N} -C = {2x|x ∈ N} +A = { x : x is a vowel } = { a, e, i, o, u, y} +B = { x : x ∈ N, x < 10 } = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } +C = { x : x = 2k, k ∈ N } = { 0, 2, 4, 6, 8, ... } ``` -## Relations between sets -### Belongs to -* If the value `a` is one of the items of the set `A`, `a` belongs to `A`. Representation: `a∈A` -* If the value `a` is not one of the items of the set `A`, `a` does not belong to `A`. Representation: `a∉A` +Sometimes the predicate may "leak" into the subject, e.g. -### Equals -* If all items in a set are exactly the same to another set, they are equal. Representation: `a=b` -* Items in a set are not order sensitive. `{1,2,3,4}={2,3,1,4}` -* Items in a set are unique. `{1,2,2,3,4,3,4,2}={1,2,3,4}` -* Two sets are equal if and only if all of their items are exactly equal to each other. Representation: `A=B`. Otherwise, they are not equal. Representation: `A≠B`. -* `A=B` if `A ⊆ B` and `B ⊆ A` +``` +D = { 2x : x ∈ N } = { 0, 2, 4, 6, 8, ... } +``` -### Belongs to -* If the set A contains an item `x`, `x` belongs to A (`x∈A`). -* Otherwise, `x` does not belong to A (`x∉A`). +## Relations -### Subsets -* If all items in a set `B` are items of set `A`, we say that `B` is a subset of `A` (`B⊆A`). -* If B is not a subset of A, the representation is `B⊈A`. +### Membership -### Proper subsets -* If `B ⊆ A` and `B ≠ A`, B is a proper subset of A (`B ⊂ A`). Otherwise, B is not a proper subset of A (`B ⊄ A`). +* If the value `a` is contained in the set `A`, then we say `a` belongs to `A` and represent this symbolically as `a ∈ A`. +* If the value `a` is not contained in the set `A`, then we say `a` does not belong to `A` and represent this symbolically as `a ∉ A`. -## Set operations -### Base number -* The number of items in a set is called the base number of that set. Representation: `|A|` -* If the base number of the set is finite, this set is a finite set. -* If the base number of the set is infinite, this set is an infinite set. +### Equality -``` -A = {A,B,C} -|A| = 3 -B = {a,{b,c}} -|B| = 2 -|∅| = 0 (it has no items) -``` +* If two sets contain the same items then we say the sets are equal, e.g. `A = B`. +* Order does not matter when determining set equality, e.g. `{ 1, 2, 3, 4 } = { 2, 3, 1, 4 }`. +* Sets are disjoint, meaning elements cannot be repeated, e.g. `{ 1, 2, 2, 3, 4, 3, 4, 2 } = { 1, 2, 3, 4 }`. +* Two sets `A` and `B` are equal if and only if `A ⊂ B` and `B ⊂ A`. -### Powerset -* Let `A` be any set. The set that contains all possible subsets of `A` is called a powerset (written as `P(A)`). +## Special Sets -``` -P(A) = {x|x ⊆ A} +### The Power Set +* Let `A` be any set. The set that contains all possible subsets of `A` is called a "power set" and is written as `P(A)`. If the set `A` contains `n` elements, then `P(A)` contains `2^N` elements. -|A| = N, |P(A)| = 2^N +``` +P(A) = { x : x ⊆ A } ``` ## Set operations among two sets @@ -111,28 +98,28 @@ P(A) = {x|x ⊆ A} Given two sets `A` and `B`, the union of the two sets are the items that appear in either `A` or `B`, written as `A ∪ B`. ``` -A ∪ B = {x|x∈A∨x∈B} +A ∪ B = { x : x ∈ A ∪ x ∈ B } ``` ### Intersection Given two sets `A` and `B`, the intersection of the two sets are the items that appear in both `A` and `B`, written as `A ∩ B`. ``` -A ∩ B = {x|x∈A,x∈B} +A ∩ B = { x : x ∈ A, x ∈ B } ``` ### Difference Given two sets `A` and `B`, the set difference of `A` with `B` is every item in `A` that does not belong to `B`. ``` -A \ B = {x|x∈A,x∉B} +A \ B = { x : x ∈ A, x ∉ B } ``` ### Symmetrical difference Given two sets `A` and `B`, the symmetrical difference is all items among `A` and `B` that doesn't appear in their intersections. ``` -A △ B = {x|(x∈A∧x∉B)∨(x∈B∧x∉A)} +A △ B = { x : ((x ∈ A) ∩ (x ∉ B)) ∪ ((x ∈ B) ∩ (x ∉ A)) } A △ B = (A \ B) ∪ (B \ A) ``` @@ -141,22 +128,5 @@ A △ B = (A \ B) ∪ (B \ A) Given two sets `A` and `B`, the cartesian product between `A` and `B` consists of a set containing all combinations of items of `A` and `B`. ``` -A × B = { {x, y} | x ∈ A, y ∈ B } -``` - -## "Generalized" operations -### General union -Better known as "flattening" of a set of sets. - -``` -∪A = {x|X∈A,x∈X} -∪A={a,b,c,d,e,f} -∪B={a} -∪C=a∪{c,d} -``` - -### General intersection - -``` -∩ A = A1 ∩ A2 ∩ … ∩ An +A × B = { (x, y) | x ∈ A, y ∈ B } ``` -- cgit v1.2.3 From 26d2733ab775e1138bfd83fe14253035275671b9 Mon Sep 17 00:00:00 2001 From: Justice Almanzar Date: Mon, 24 Aug 2020 16:45:36 -0400 Subject: correct equality statement --- set-theory.html.markdown | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'set-theory.html.markdown') diff --git a/set-theory.html.markdown b/set-theory.html.markdown index 6fb657ed..e292464c 100644 --- a/set-theory.html.markdown +++ b/set-theory.html.markdown @@ -82,7 +82,7 @@ D = { 2x : x ∈ N } = { 0, 2, 4, 6, 8, ... } * If two sets contain the same items then we say the sets are equal, e.g. `A = B`. * Order does not matter when determining set equality, e.g. `{ 1, 2, 3, 4 } = { 2, 3, 1, 4 }`. * Sets are disjoint, meaning elements cannot be repeated, e.g. `{ 1, 2, 2, 3, 4, 3, 4, 2 } = { 1, 2, 3, 4 }`. -* Two sets `A` and `B` are equal if and only if `A ⊂ B` and `B ⊂ A`. +* Two sets `A` and `B` are equal if and only if `A ⊆ B` and `B ⊆ A`. ## Special Sets -- cgit v1.2.3 From 7d927011da46e767371334a54ab9e6bca6730f7f Mon Sep 17 00:00:00 2001 From: Pavitra Golchha Date: Tue, 29 Sep 2020 12:21:58 +0530 Subject: Fix: Cardinality of an empty set is 0 Citations: - JMoravitz (https://math.stackexchange.com/users/179297/jmoravitz), What is the cardinality of the set of the empty set?, URL (version: 2016-01-13): https://math.stackexchange.com/q/1610231 - Wikipedia contributors. (2020, September 25). Empty set. In Wikipedia, The Free Encyclopedia. Retrieved 06:50, September 29, 2020, from https://en.wikipedia.org/w/index.php?title=Empty_set&oldid=980302053 --- set-theory.html.markdown | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'set-theory.html.markdown') diff --git a/set-theory.html.markdown b/set-theory.html.markdown index 6fb657ed..1894c306 100644 --- a/set-theory.html.markdown +++ b/set-theory.html.markdown @@ -44,7 +44,7 @@ For example, if `S = { 1, 2, 4 }`, then `|S| = 3`. * The empty set can be constructed in set builder notation using impossible conditions, e.g. `∅ = { x : x =/= x }`, or `∅ = { x : x ∈ N, x < 0 }`; * the empty set is always unique (i.e. there is one and only one empty set); * the empty set is a subset of all sets; -* the cardinality of the empty set is 1, i.e. `|∅| = 1`. +* the cardinality of the empty set is 0, i.e. `|∅| = 0`. ## Representing sets -- cgit v1.2.3