Cardinality.html (1775B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.0.3 (456341)"/><meta name="keywords" content="sets"/><meta name="altitude" content="-1.531793236732483"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-03-08 16:20:26 +0000"/><meta name="latitude" content="52.33418990626854"/><meta name="longitude" content="4.867487486548002"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-03-08 16:28:07 +0000"/><title>Cardinality</title></head><body><div><b>Cardinality (notion of size)</b></div><div>|A| cardinality of A (size)</div><div><ul><li>|A| ≤ |B| ⟷ there exists a total injection f: A ➝ B</li><li>|A| = |B| ⟷ there exists a bijection f: A ➝ B</li><li>|A| = #A = m ⟷ there exists a bijection f: {1,…,m} ➝ A</li></ul><div><br/></div></div><div><b>Cantor-Schroeder-Bernstein theorem (partial ordering of sets)</b></div><div>if there exist total injective functions f: A ➝ B, g: B ➝ A</div><div>then there exists a bijection h: A ➝ B</div><div><br/></div><div>so sets can be partially ordered by cardinality.</div><div><br/></div><div><b>Countable/Uncountable</b></div><div>set A is:</div><div><ul><li>countably infinite — there exists a bijection f: Nat ➝ A</li><li>countable — A is finite or countably infinite</li><li>uncountable — A is not countable</li></ul></div><div><br/></div><div>if a set is countable, it can be enumerated</div><div><br/></div><div><br/></div></body></html>