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 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7e629fa6598d732768f7c726b4b621285f9c3b85303900aa912017db7617d8bdb disjoint from 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7b17ef6d19c7a5b1ee83b907c595526dcb1eb06db8227d650d5dda0a9f4ce8cd9.
  3. Schema of Comprehension: Given a set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc74523540f1504cd17100c4835e85b7eefd49911580f8efff0599a8f283be6b9e3 and a formula 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc74ec9599fc203d176a301536c2e091a19bc852759b255bd6818810a42c5fed14a, the set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc79400f1b21cb527d7fa3d3eabba93557a18ebe7a2ca4e471cfe5e4c5b4ca7f767 exists.
  4. Pairing: if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7f5ca38f748a1d6eaf726b8a42fb575c3c71f1864a8143301782de13da2d9202b and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc76f4b6612125fb3a0daecd2799dfd6c9c299424fd920f9b308110a2c1fbd8f443 exist, then there is a set containing both 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7785f3ec7eb32f30b90cd0fcf3657d388b5ff4297f2f9716ff66e9b69c05ddd09 and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7535fa30d7e25dd8a49f1536779734ec8286108d115da5045d77f3b4185d8f790.
  5. Union: the union over the elements of a set exists. That is, if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7c2356069e9d1e79ca924378153cfbbfb4d4416b1f99d41a2940bfdb66c5319db then the set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7b7a56873cd771f2c446d369b649430b65a756ba278ff97ec81bb6f55b2e73569 exists.
  6. Replacement: informally if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc75f9c4ab08cac7457e9111a30e4664920607ea2c115a1433d7be98e97e64244ca is a function definable by a formula 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7670671cd97404156226e507973f2ab8330d3022ca96e0c93bdbdb320c41adcaf, 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc759e19706d51d39f66711c2653cd7eb1291c94d9b55eb14bda74ce4dc636d015a is a set, and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc735135aaa6cc23891b40cb3f378c53a17a1127210ce60e125ccf03efcfdaec458 exists for all 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7624b60c58c9d8bfb6ff1886c2fd605d2adeb6ea4da576068201b6c6958ce93f4, then the set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7eb1e33e8a81b697b75855af6bfcdbcbf7cbbde9f94962ceaec1ed8af21f5a50f exists.
  7. Infinity: there is a set containing 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7e29c9c180c6279b0b02abd6a1801c7c04082cf486ec027aa13515e4f3884bb6b and closed under the successor operation 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7c6f3ac57944a531490cd39902d0f777715fd005efac9a30622d5f5205e7f6894.
  8. Power set: if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc786e50149658661312a9e0b35558d84f6c6d3da797f552a9657fe0558ca40cdef is a set, then so is the set of all subsets of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc79f14025af0065b30e47e23ebb3b491d39ae8ed17d33739e5ff3827ffb3634953, which we call the power set of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc776a50887d8f1c2e9301755428990ad81479ee21c25b43215cf524541e0503269 and denote it by 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc77a61b53701befdae0eeeffaecc73f14e20b537bb0f8b91ad7c2936dc63562b25.
  9. Choice (AC): the cartesian product of a collection of nonempty sets is nonempty.
  10. Or equivalent to AC: for every set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7aea92132c4cbeb263e6ac2bf6c183b5d81737f179f21efdc5863739672f0f470 there is a binary relation on 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc70b918943df0962bc7a1824c0555a389347b4febdc7cf9d1254406d80ce44e3f9 which makes 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7d59eced1ded07f84c145592f65bdf854358e009c5cd705f5215bf18697fed103 well-ordered.

Relations and functions

Given sets 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc73d914f9348c9cc0ff8a79716700b9fcd4d2f3e711608004eb8f138bcba7f14d9 and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc773475cb40a568e8da8a045ced110137e159f890ac4da883b6b17dc651b3a8049, the cartesian product of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc744cb730c420480a0477b505ae68af508fb90f96cf0ec54c6ad16949dd427f13a and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc771ee45a3c0db9a9865f7313dd3372cf60dca6479d46261f3542eb9346e4a04d6, denoted 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7811786ad1ae74adfdd20dd0372abaaebc6246e343aebd01da0bfc4c02bf0106c is the set of all pairs 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc725fc0e7096fc653718202dc30b0c580b8ab87eac11a700cba03a7c021bc35b0c such that 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc731489056e0916d59fe3add79e63f095af3ffb81604691f21cad442a85c7be617 and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc798010bd9270f9b100b6214a21754fd33bdc8d41b2bc9f9dd16ff54d3c34ffd71. That is: 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc70e17daca5f3e175f448bacace3bc0da47d0655a74c8dd0dc497a3afbdad95f1f. Similarly we define the cartesian product of many sets 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc71a6562590ef19d1045d06c4055742d38288e9e6dcd71ccde5cee80f1d5a774eb. The cartesian product of an infinite collection of sets 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7031b4af5197ec30a926f48cf40e11a7dbc470048a21e4003b7a3c07c5dab1baa where 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc741cfc0d1f2d127b04555b7246d84019b4d27710a3f3aff6e7764375b1e06e05d is an infinite index set, is more fiddly to define (essentially elements of the cartesian product of an infinite collection of sets are functions 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc72858dcd1057d3eae7f7d5f782167e24b61153c01551450a628cee722509f6529 such that for all 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc72fca346db656187102ce806ac732e06a62df0dbb2829e511a770556d398e1a6e we have 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc702d20bbd7e394ad5999a4cebabac9619732c343a4cac99470c03e23ba2bdc2bc).

A 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc77688b6ef52555962d008fff894223582c484517cea7da49ee67800adc7fc8866-ary relation on a set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7c837649cce43f2729138e72cc315207057ac82599a59be72765a477f22d14a54 is a subset of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc76208ef0f7750c111548cf90b6ea1d0d0a66f6bff40dbef07cb45ec436263c7d6 where the cartesian product is of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc73e1e967e9b793e908f8eae83c74dba9bcccce6a5535b4b462bd9994537bfe15c copies of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc739fa9ec190eee7b6f4dff1100d6343e10918d044c75eac8f9e9a2596173f80c9.

A function 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7d029fa3a95e174a19934857f535eb9427d967218a36ea014b70ad704bc6c8d1c is a relation 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc781b8a03f97e8787c53fe1a86bda042b6f0de9b0ec9c09357e107c99ba4d6948a on 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7da4ea2a5506f2693eae190d9360a1f31793c98a1adade51d93533a6f520ace1c, such that 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7a68b412c4282555f15546cf6e1fc42893b7e07f271557ceb021821098dd66c1b associates an element of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7108c995b953c8a35561103e2014cf828eb654a99e310f87fab94c2f4b7d2a04f to at most one element of 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc73ada92f28b4ceda38562ebf047c6ff05400d4c572352a1142eedfef67d21e662. That is, if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc749d180ecf56132819571bf39d9b7b342522a2ac6d23c1418d3338251bfe469c8 and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7a21855da08cb102d1d217c53dc5824a3a795c1c1a44e971bf01ab9da3a2acbbf then necessarily 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7c75cb66ae28d8ebc6eded002c28a8ba0d06d3a78c6b5cbf9b2ade051f0775ac4. When 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7ff5a1ae012afa5d4c889c50ad427aaf545d31a4fac04ffc1c4d03d403ba4250a defines a function, we use the notation 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc77f2253d7e228b22a08bda1f09c516f6fead81df6536eb02fa991a34bb38d9be8.

Properties of functions

A function is injective if different inputs give different outputs. That is, if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc78722616204217eddb39e7df969e0698aed8e599ba62ed2de1ce49b03ade0fede and 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc796061e92f58e4bdcdee73df36183fe3ac64747c81c26f6c83aada8d2aabb1864 then 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7eb624dbe56eb6620ae62080c10a273cab73ae8eca98ab17b731446a31c79393a.

A function is surjective if its codomain is equal to its range. That is, if 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7f369cb89fc627e668987007d121ed1eacdc01db9e28f8bb26f358b7d8c4f08ac then for all 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7f74efabef12ea619e30b79bddef89cffa9dda494761681ca862cff2871a85980 there is 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7a88a7902cb4ef697ba0b6759c50e8c10297ff58f942243de19b984841bfe1f73 with 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7349c41201b62db851192665c504b350ff98c6b45fb62a8a2161f78b6534d8de9.

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

Ordinals

We can construct the natural numbers by identifying 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc798a3ab7c340e8a033e7b37b6ef9428751581760af67bbab2b9e05d4964a8874a with the empty set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc748449a14a4ff7d79bb7a1b6f3d488eba397c36ef25634c111b49baf362511afc, and the proceeding to define the successor 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc75316ca1c5ddca8e6ceccfce58f3b8540e540ee22f6180fb89492904051b3d531. This way we get an ordinal for each natural number 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7a46e37632fa6ca51a13fe39a567b3c23b28c2f47d8af6be9bd63e030e214ba38. These are the finite ordinals. We can take the union of all finite ordinals to get the first infinite ordinal, which we denote 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7bbb965ab0c80d6538cf2184babad2a564a010376712012bd07b0af92dcd3097d.

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 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc744c8031cb036a7350d8b9b8603af662a4b9cdbd2f96e8d5de5af435c9c35da69 and an injection 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7b4944c6ff08dc6f43da2e9c824669b7d927dd1fa976fadc7b456881f51bf5ccc then there exists a bijection 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7434c9b5ae514646bbd91b50032ca579efec8f22bf0b4aac12e65997c418e0dd6.

We denote the cardinality of a set 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7bdd2d3af3a5a1213497d4f1f7bfcda898274fe9cb5401bbc0190885664708fc2 by 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc78b940be7fb78aaa6b6567dd7a3987996947460df1c668e698eb92ca77e425349, and we identify 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc7cd70bea023f752a0564abb6ed08d42c1440f2e33e29914e55e0be1595e24f45a with the smallest ordinal 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc769f59c273b6e669ac32a6dd5e1b2cb63333d8b004f9696447aee2d422ce63763 such that 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc71da51b8d8ff98f6a48f80ae79fe3ca6c26e1abb7b7d125259255d6d2b875ea08 is equinumerous with 4621cb85cbac7732baa0274413c8956703a3f5718b6e346cd873482364fffbc78241649609f88ccd2a0a5b233a07a538ec313ff6adf695aa44a969dbca39f67d.

If we assume the Axiom of Choice, or equivalently, the well-ordering principle,