maths/pure/ AbstractSetTheory101

Here is a rough overview of the basics of AbstractSetTheory, in particular ZFC and how we construct things like numbers and functions.

What is 'abstract' about Abstract Set Theory?

We never worry about, or ask about, what sets actually are. In the formal language of SetTheory, there is only one non-logical symbol: ∈. Abstract set theory is all about the relation ∈. We begin with a set of a priori assumptions about properties that any sensible notion of ∈ should satisfy. We call these axioms. There are a few different sets of axioms for Set Theory, but the most common is ZFC (Zermelo-Fraenkel with the AxiomOfChoice).

Axioms

  1. Extensionality: two sets are equal if and only if they have the same elements.
  2. Regularity: every non-empty set contains an element 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f535fa30d7e25dd8a49f1536779734ec8286108d115da5045d77f3b4185d8f790 disjoint from 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fc2356069e9d1e79ca924378153cfbbfb4d4416b1f99d41a2940bfdb66c5319db.
  3. Schema of Comprehension: Given a set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fb7a56873cd771f2c446d369b649430b65a756ba278ff97ec81bb6f55b2e73569 and a formula 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f5f9c4ab08cac7457e9111a30e4664920607ea2c115a1433d7be98e97e64244ca, the set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f670671cd97404156226e507973f2ab8330d3022ca96e0c93bdbdb320c41adcaf exists.
  4. Pairing: if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f59e19706d51d39f66711c2653cd7eb1291c94d9b55eb14bda74ce4dc636d015a and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f35135aaa6cc23891b40cb3f378c53a17a1127210ce60e125ccf03efcfdaec458 exist, then there is a set containing both 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f624b60c58c9d8bfb6ff1886c2fd605d2adeb6ea4da576068201b6c6958ce93f4 and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355feb1e33e8a81b697b75855af6bfcdbcbf7cbbde9f94962ceaec1ed8af21f5a50f.
  5. Union: the union over the elements of a set exists. That is, if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fe29c9c180c6279b0b02abd6a1801c7c04082cf486ec027aa13515e4f3884bb6b then the set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fc6f3ac57944a531490cd39902d0f777715fd005efac9a30622d5f5205e7f6894 exists.
  6. Replacement: informally if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f86e50149658661312a9e0b35558d84f6c6d3da797f552a9657fe0558ca40cdef is a function definable by a formula 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f9f14025af0065b30e47e23ebb3b491d39ae8ed17d33739e5ff3827ffb3634953, 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f76a50887d8f1c2e9301755428990ad81479ee21c25b43215cf524541e0503269 is a set, and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f7a61b53701befdae0eeeffaecc73f14e20b537bb0f8b91ad7c2936dc63562b25 exists for all 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355faea92132c4cbeb263e6ac2bf6c183b5d81737f179f21efdc5863739672f0f470, then the set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f0b918943df0962bc7a1824c0555a389347b4febdc7cf9d1254406d80ce44e3f9 exists.
  7. Infinity: there is a set containing 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fd59eced1ded07f84c145592f65bdf854358e009c5cd705f5215bf18697fed103 and closed under the successor operation 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f3d914f9348c9cc0ff8a79716700b9fcd4d2f3e711608004eb8f138bcba7f14d9.
  8. Power set: if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f73475cb40a568e8da8a045ced110137e159f890ac4da883b6b17dc651b3a8049 is a set, then so is the set of all subsets of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f44cb730c420480a0477b505ae68af508fb90f96cf0ec54c6ad16949dd427f13a, which we call the power set of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f71ee45a3c0db9a9865f7313dd3372cf60dca6479d46261f3542eb9346e4a04d6 and denote it by 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f811786ad1ae74adfdd20dd0372abaaebc6246e343aebd01da0bfc4c02bf0106c.
  9. Choice (AC): the cartesian product of a collection of nonempty sets is nonempty.
  10. Or equivalent to AC: for every set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f25fc0e7096fc653718202dc30b0c580b8ab87eac11a700cba03a7c021bc35b0c there is a binary relation on 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f31489056e0916d59fe3add79e63f095af3ffb81604691f21cad442a85c7be617 which makes 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f98010bd9270f9b100b6214a21754fd33bdc8d41b2bc9f9dd16ff54d3c34ffd71 well-ordered.

Relations and functions

Given sets 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f0e17daca5f3e175f448bacace3bc0da47d0655a74c8dd0dc497a3afbdad95f1f and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f1a6562590ef19d1045d06c4055742d38288e9e6dcd71ccde5cee80f1d5a774eb, the cartesian product of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f031b4af5197ec30a926f48cf40e11a7dbc470048a21e4003b7a3c07c5dab1baa and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f41cfc0d1f2d127b04555b7246d84019b4d27710a3f3aff6e7764375b1e06e05d, denoted 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f2858dcd1057d3eae7f7d5f782167e24b61153c01551450a628cee722509f6529 is the set of all pairs 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f2fca346db656187102ce806ac732e06a62df0dbb2829e511a770556d398e1a6e such that 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f02d20bbd7e394ad5999a4cebabac9619732c343a4cac99470c03e23ba2bdc2bc and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f7688b6ef52555962d008fff894223582c484517cea7da49ee67800adc7fc8866. That is: 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fc837649cce43f2729138e72cc315207057ac82599a59be72765a477f22d14a54. Similarly we define the cartesian product of many sets 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f6208ef0f7750c111548cf90b6ea1d0d0a66f6bff40dbef07cb45ec436263c7d6. The cartesian product of an infinite collection of sets 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f3e1e967e9b793e908f8eae83c74dba9bcccce6a5535b4b462bd9994537bfe15c where 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f39fa9ec190eee7b6f4dff1100d6343e10918d044c75eac8f9e9a2596173f80c9 is an infinite index set, is more fiddly to define (essentially elements of the cartesian product of an infinite collection of sets are functions 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fd029fa3a95e174a19934857f535eb9427d967218a36ea014b70ad704bc6c8d1c such that for all 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f81b8a03f97e8787c53fe1a86bda042b6f0de9b0ec9c09357e107c99ba4d6948a we have 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fda4ea2a5506f2693eae190d9360a1f31793c98a1adade51d93533a6f520ace1c).

A 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fa68b412c4282555f15546cf6e1fc42893b7e07f271557ceb021821098dd66c1b-ary relation on a set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f108c995b953c8a35561103e2014cf828eb654a99e310f87fab94c2f4b7d2a04f is a subset of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f3ada92f28b4ceda38562ebf047c6ff05400d4c572352a1142eedfef67d21e662 where the cartesian product is of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f49d180ecf56132819571bf39d9b7b342522a2ac6d23c1418d3338251bfe469c8 copies of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fa21855da08cb102d1d217c53dc5824a3a795c1c1a44e971bf01ab9da3a2acbbf.

A function 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fc75cb66ae28d8ebc6eded002c28a8ba0d06d3a78c6b5cbf9b2ade051f0775ac4 is a relation 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fff5a1ae012afa5d4c889c50ad427aaf545d31a4fac04ffc1c4d03d403ba4250a on 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f7f2253d7e228b22a08bda1f09c516f6fead81df6536eb02fa991a34bb38d9be8, such that 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f8722616204217eddb39e7df969e0698aed8e599ba62ed2de1ce49b03ade0fede associates an element of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f96061e92f58e4bdcdee73df36183fe3ac64747c81c26f6c83aada8d2aabb1864 to at most one element of 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355feb624dbe56eb6620ae62080c10a273cab73ae8eca98ab17b731446a31c79393a. That is, if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355ff369cb89fc627e668987007d121ed1eacdc01db9e28f8bb26f358b7d8c4f08ac and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355ff74efabef12ea619e30b79bddef89cffa9dda494761681ca862cff2871a85980 then necessarily 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fa88a7902cb4ef697ba0b6759c50e8c10297ff58f942243de19b984841bfe1f73. When 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f349c41201b62db851192665c504b350ff98c6b45fb62a8a2161f78b6534d8de9 defines a function, we use the notation 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f98a3ab7c340e8a033e7b37b6ef9428751581760af67bbab2b9e05d4964a8874a.

Properties of functions

A function is injective if different inputs give different outputs. That is, if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f48449a14a4ff7d79bb7a1b6f3d488eba397c36ef25634c111b49baf362511afc and 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f5316ca1c5ddca8e6ceccfce58f3b8540e540ee22f6180fb89492904051b3d531 then 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fa46e37632fa6ca51a13fe39a567b3c23b28c2f47d8af6be9bd63e030e214ba38.

A function is surjective if its codomain is equal to its range. That is, if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fbbb965ab0c80d6538cf2184babad2a564a010376712012bd07b0af92dcd3097d then for all 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f44c8031cb036a7350d8b9b8603af662a4b9cdbd2f96e8d5de5af435c9c35da69 there is 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fb4944c6ff08dc6f43da2e9c824669b7d927dd1fa976fadc7b456881f51bf5ccc with 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f434c9b5ae514646bbd91b50032ca579efec8f22bf0b4aac12e65997c418e0dd6.

A function is bijective if it is both injective and surjective.

Ordinals

We can construct the natural numbers by identifying 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fbdd2d3af3a5a1213497d4f1f7bfcda898274fe9cb5401bbc0190885664708fc2 with the empty set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f8b940be7fb78aaa6b6567dd7a3987996947460df1c668e698eb92ca77e425349, and the proceeding to define the successor 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fcd70bea023f752a0564abb6ed08d42c1440f2e33e29914e55e0be1595e24f45a. This way we get an ordinal for each natural number 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f69f59c273b6e669ac32a6dd5e1b2cb63333d8b004f9696447aee2d422ce63763. These are the finite ordinals. We can take the union of all finite ordinals to get the first infinite ordinal, which we denote 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f1da51b8d8ff98f6a48f80ae79fe3ca6c26e1abb7b7d125259255d6d2b875ea08. We call these limit ordinals. Once we have 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f8241649609f88ccd2a0a5b233a07a538ec313ff6adf695aa44a969dbca39f67d, we can construct 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f6e4001871c0cf27c7634ef1dc478408f642410fd3a444e2a88e301f5c4a35a4d), which we denote 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fe3d6c4d4599e00882384ca981ee287ed961fa5f3828e2adb5e9ea890ab0d0525, and then 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fad48ff99415b2f007dc35b7eb553fd1eb35ebfa2f2f308acd9488eeb86f71fa8 and so on. Then we can take the union of all the 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f7b1a278f5abe8e9da907fc9c29dfd432d60dc76e17b0fabab659d2a508bc65c4 to get 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fd6d824abba4afde81129c71dea75b8100e96338da5f416d2f69088f1960cb091, which we denote 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f29db0c6782dbd5000559ef4d9e953e300e2b479eed26d887ef3f92b921c06a67. In this way, we can create bigger and bigger ordinals. Either using the successor operation or taking unions to produce limit ordinals. Ordinals are well-ordered. That is, a set of ordinals does not contain an infinite descending sequence.

Cardinals

The cardinality of a set is the 'number' of elements in it. It can be infinite. Two sets have the same cardinality, that is, they are equinumerous if, and only if, there exists a bijective function between them.

The Schröder-Bernstein Theorem says that if there exists an injection 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f8c1f1046219ddd216a023f792356ddf127fce372a72ec9b4cdac989ee5b0b455 and an injection 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fad57366865126e55649ecb23ae1d48887544976efea46a48eb5d85a6eeb4d306 then there exists a bijection 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f16dc368a89b428b2485484313ba67a3912ca03f2b2b42429174a4f8b3dc84e44.

We denote the cardinality of a set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f37834f2f25762f23e1f74a531cbe445db73d6765ebe60878a7dfbecd7d4af6e1 by 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f454f63ac30c8322997ef025edff6abd23e0dbe7b8a3d5126a894e4a168c1b59b, and we identify 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f5ef6fdf32513aa7cd11f72beccf132b9224d33f271471fff402742887a171edf with the smallest ordinal 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f1253e9373e781b7500266caa55150e08e210bc8cd8cc70d89985e3600155e860 such that 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f482d9673cfee5de391f97fde4d1c84f9f8d6f2cf0784fcffb958b4032de7236c is equinumerous with 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f3346f2bbf6c34bd2dbe28bd1bb657d0e9c37392a1d5ec9929e6a5df4763ddc2d. The cardinal of the set of all finite ordinals is denoted 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f9537f32ec7599e1ae953af6c9f929fe747ff9dadf79a9beff1f304c550173011, (aleph null), and (assuming AC) is the smallest infinite ordinal.

If we assume the Axiom of Choice, or equivalently, the well-ordering principle, then every set is equinumerous with some ordinal, and so the cardinals are linearly ordered.

Countability

A set is countable if either it is finite or else its cardinality is 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f0fd42b3f73c448b34940b339f87d07adf116b05c0227aad72e8f0ee90533e699. Equivalently, a set X is countable if it is the image of some function from 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f9bdb2af6799204a299c603994b8e400e4b1fd625efdb74066cc869fee42c9df3. That is, if 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355ff6e0a1e2ac41945a9aa7ff8a8aaa0cebc12a3bcc981a929ad5cf810a090e11ae.

The power set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fb1556dea32e9d0cdbfed038fd7787275775ea40939c146a64e205bcb349ad02f of a set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f6c658ee83fb7e812482494f3e416a876f63f418a0b8a1f5e76d47ee4177035cb is always of a larger cardinality than 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f9f1f9dce319c4700ef28ec8c53bd3cc8e6abe64c68385479ab89215806a5bdd6, as can be proved by Cantor's Diagonal Argument. The real numbers 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f28dae7c8bde2f3ca608f86d0e16a214dee74c74bee011cdfdd46bc04b655bc14 are at least as large as the power set 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355fe5b861a6d8a966dfca7e7341cd3eb6be9901688d547a72ebed0b1f5e14f3d08d of the natural numbers, so are strictly larger (in cardinality terms), than 2142e4d1a481d78bc0fea57cdb5cc40dad4c805a331170a8f3bfbebc0e8b355f2ac878b0e2180616993b4b6aa71e61166fdc86c28d47e359d0ee537eb11d46d3.