Set Theory, An Open Introduction (Tim Button)

(link)

61 flashcards · Mathematics · by lakesare

1. Name a single famous theorem by: Gödel VS Kurt Friedrich Gödel (1906 - 1978, died in US)Cantor Georg Cantor (1845 - 1918, died in Germany)

   Gödel - Gödel incompleteness theorems The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.Cantor - Cantor's Diagonalization Theorem Cantor - Uncountable

2. [Axioms] Visually imagine the Axiom of Extensionality.

3. [Axioms] Why is the Axiom of Extensionality called so?

   Because we're: interested in the members (== extension) of the set, and not interested in how the set was formed (== intension).

4. [Notation] What does B denote?

5. [Notation] What does 𝛬 (lambda) denote here?

   An empty string.

6. [Notation] What do these denote: A* A𝜔

   A* - { ...all finite strings } B∗ = { 𝛬, 0, 1, 00, 01, 10, 11, 000, ... }A𝜔 - { ...all infinite strings } A𝜔 = { 0~, 1~, 0101~, ... } It's possible to have a set of: { ...all finite strings }, { ...all infinite strings }, { ...all finite and infinite strings }.

7. [Notation] What does A\B denote?

   Set difference (A – B)

8. [Notation] Name 2 ways to name this:

   ordered pair 2-tuple

9. [N-tuples] Expand ⟨a, b⟩ using the Kuratowski definition.

   We can define ordered pairs in set theory using the Wiener-Kuratowski definition.

10. [N-tuples] Visually imagine the definition of 3-tuple using 2-tuples.

    We can think of triples as special ordered pairs, where the first element is itself an ordered pair: ⟨x, y, z ⟩ is ⟨⟨x, y⟩, z ⟩. The same is true for quadruples: ⟨x, y, z ,u⟩ is ⟨⟨⟨x, y⟩, z ⟩,u⟩, and so on.

11. [N-tuples] Visually imagine why tuples ≠ arrays.

    BUT [x, y, z] is NOT [[x, y], z].

12. [N-tuples] Visually imagine 2 forms of the Cartesian Product A×B×C.

    { ⟨x, y, z⟩ : ~} { ⟨⟨x, y⟩, z⟩ : ~} These are the same forms!

13. [Naivety] What's strange about this definition of the set: S = { x : 𝜑(x) }?

    𝜑 is supposed to be any property, however this allows for Russell's paradox!

14. [Russell's Paradox] Visually imagine Russell's Paradox.

    Naive set theory tells us all sets exist S = { x : 𝜑(x) }BUT set R = { x : x ∉ x } does NOT exist!

15. [Naivety] In what sense is the naive set theory "genuinely naive"?

    It allows for Russell's paradox because it doesn't specify which sets can and cannot exist. Naive set theory allows any set S = { x : 𝜑(x) }.

16. [Relations] Visually imagine a relation on N. The set N2 of pairs of natural numbers can be listed in a 2-dimensional matrix.

    Any subset of N⨯N is a relation!

17. [Relations] Visually imagine: empty relation on A universal relation on A

    empty relation - ∅ universal relation - A2

18. [Relations] What does IdA denote?

    Identity relation on A. IdN = {⟨0, 0⟩, ⟨1, 1⟩, ⟨2, 2⟩, . . . } is the identity relation on N.

19. [Relations] Visually imagine the identity relation on N IdN.

    IdN = {⟨0, 0⟩, ⟨1, 1⟩, ⟨2, 2⟩, . . . } is the identity relation on N.

20. [Relations] What is the Benacerraf's argument against set-theoretic reductionism?

    We can define ordered pairs as either ⟨a, b⟩ or ∥a, b∥: When a ≠ b, we have that ⟨a,b⟩ ≠ ∥a,b ∥. But we could equally have regarded ∥a,b ∥ as our definition of an ordered pair, rather than ⟨a,b⟩. Both definitions would have worked equally well. So now we have two equally good candidates to “be” the order relation on the natural numbers.But when we expand them, relations will be unequal! Since R ≠ S , by extensionality, it is clear that they cannot both be identical to the order relation on N. B…

21. [Relations] Name 2 important types of relations (that have a combination of these properties). Reflexive, Transitive, Symmetric, Connective, Anti-Symmetric, Asymmetric, Irreflexive.

    Equivalence relations (RST - Reflexive Symmetric Transitive)Order relations It turns out that (combinations of) some of these special properties are especially important: orders and equivalence relations.

22. [Relations] When are x and y said to be R-equivalent?

    R is an equivalence relation Rxy

23. [Relations] Visually imagine: equivalence relation VS equivalence class. Equivalence relation is defined by these arrows.

    equivalence relation - { ...arrows } equivalence class - { ...elements } Equivalence class = equivalence relation instantiated with a particular x!

24. [Relations] How do you read [x]R?

    The equivalence class of x. [x]R = { y ∈ A : Rxy }.

25. [Relations] How do you read A/R?

    Quotient of A under R. A/R = { [x]R : x ∈ A }.

26. [Relations] What exactly is a "quotient of A under R".

    { eq. class, eq. class, eq. class, ... } in A under R.

27. [Relations] What does ", by extensionality," mean?

    It means "by set equality definition".

28. [Relation properties] Give a stereotype for "connected" relation property.

    All disparate nodes are in some way connected.

29. [Relation properties] Give a stereotype for "irreflexive" relation property.

    Prohibit even trying reflection!

30. [Relation properties] Give a stereotype for "asymmetric" relation property.

    Prohibit even trying symmetry!

31. [Relation properties] Give a stereotype for "anti-symmetric" relation property.

    Prohibit even trying symmetry UNLESS x=y.

32. [Functions] What's an "injection from A to B"?

    f: A → B that's one-to-one

33. [Functions] What's a "surjection from A to B"?

    f: A → B that's onto

34. [Size of sets] Visually imagine an enumeration of set A.

    Bijection f: A → ℕ/some subset of ℕ Equivalently, bijection f: ℕ/some subset of ℕ → A There is an intuitive underpinning to this use of the word enumeration. For to say that we have enumerated a set A is to say that there is a bijection f which allows us to count out the elements of the set A. The 0th element is f (0), the 1st is f (1), . . . the nth is f (n). . .

35. [Size of sets] When is a set A "countable"?

    There exists an enumeration of A Enumeration of A is a bijection f: A → ℕ.

36. [Size of sets] How are these connected: countability of a set enumeration of a set

    A is countable when there EXISTS an enumeration of A Enumeration of A is a bijection f: A → ℕ/some subset of ℕ

37. [Size of sets] Visually imagine the enumeration of ℕ × ℕ.

    Use Cantor's Zig-Zag Method. This would enable us to calculate exactly where ⟨n,m⟩ will occur in our enumeration. In fact, we can define g directly by making two observations. First: if the nth row and mth column contains value v, then the (n+1)st row and (m−1)st column contains value v +1. Second: the first row of our enumeration consists of the triangular numbers, starting with 0, 1, 3, 6, etc. The k th triangular number is the sum of the natural numbers < k , which can be computed as k (k +1…

38. [Size of sets] Visually imagine some pairing function.

    Injective f: A × B → ℕ In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number.

39. [Size of sets] How can we show that a set is: countable uncountable?

    countable - find the enumeration For example you can find the enumeration via Cantor's Zig-Zag Method.uncountable - Cantor's Diagonalization Method OR But here’s another way we can prove that ℘(N) is uncountable: show that if ℘(N) is countable then B𝜔 is also countable. Since we know B𝜔 is uncountable, it will follow that ℘(N) is too.

40. [Size of sets] Visually imagine: Cantor's Zig-Zag Method Cantor's Diagonal Method

    Cantor's Zig-Zag Method - shows S is countable by finding a particular enumeration. Cantor's Diagonal Method - shows S is uncountable by finding a devilish element.

41. [Size of sets] What does A ≈ B denote?

    Set A is equinumerous with B.

42. [Size of sets] When is the set A equinumerous with the set B?

    When there exists a bijection f: A → B.

43. [Size of sets] When is the set A ⪯ B?

44. [Size of sets] When is the set A ≺ B? A is smaller than B.

    There exists an injection f: A → B (so A ⪯ B) But NO bijection g: A → B (NOT A ≈ B)

45. [Size of sets] Visually imagine the analogy: Frege proposed for comparing sizes of sets Gottlob Frege (Germany, 1848 - 1925)

46. [Size of sets] Visually imagine the Schröder-Bernstein Theorem.

    In other words, if there is an injection from A to B, and an injection from B to A, then there is a bijection from A to B. This result, however, is really rather difficult to prove. Indeed, although Cantor stated the result, others proved it

47. [Size of sets] How is the Schröder-Bernstein Theorem useful?

    It can be hard to find a bijection, and easier to find: injection from A to B AND injection from B to A.

48. [Size of sets, Axioms] What's Axiom of Extensionality VS Schröder-Bernstein Theorem?

    Axiom of Extensionality Schröder-Bernstein Theorem

49. [Arithmetization] What is arithmetization?

    When we recreate mathematics just with natural numbers. Arithmetization is a treatment of mathematics by methods involving only the fundamental concepts and operations of arithmetic. Arithmetization is a method used in mathematical logic for replacing a reasoning on the expressions of some logico-mathematical language by reasonings on natural numbers.The term "arithmetization" (in the phrase "arithmetization of analysis" ) is also used in the literature on the foundations of mathematics to deno…

50. [Notation] What does [m, n]∼ denote?

    [⟨m, n⟩]∼

51. [Arithmetization] Visually imagine how to go: from natural numbers (ℕ) to integer (ℤ).

    int = [⟨a, b⟩]~ = equivalence class under ~, where ⟨a, b⟩ ~ ⟨c, d⟩ iff a – b = c – d.

52. [Arithmetization] Visually imagine how to go: from integers (ℤ) to rational (ℚ).

53. [√2 is rational - geometric proof by Tennenbaum] Visually imagine why: the area of the orange square == the area of 2 white squares. Suppose, for reductio, that √2 is rational. So √2 = m/n for some natural numbers m and n. Indeed, we can choose m and n so that the fraction cannot be reduced any further.

    The orange square gets *squeezed out* into white squares.

54. [√2 is rational - geometric proof by Tennenbaum] Visually imagine why: the area of the orange square == the area of 2 white squares. Suppose, for reductio, that √2 is rational. So √2 = m/n for some natural numbers m and n. Indeed, we can choose m and n so that the fraction cannot be reduced any further.

    The orange square gets *squeezed out* into white squares. Imagine two pieces of paper (red and yellow) laid on top of each other.Then, cut out the intersection, and put it into the white squares.

55. [√2 is rational - geometric proof by Tennenbaum] Visually imagine the proof.

    ASSUME square = 2 yellow squares (Which is equivalent to saying we found m2 = 2n2, and we're looking for a contradiction)THEN middle square = 2 white squares Because the middle square gets squeezed out.This means that there are numbers smaller than m and n that have m2 = 2n2 property. But we thought we took the smallest possible numbers! Contradiction.

56. [Completeness Property] What's the difference between: rationals (ℚ) VS reals (ℝ)?

    Because reals have the Completeness Property!

57. [Completeness Property] State the Completeness Property of the real numbers (ℝ).

    For any E = { ~reals }: if E has an upper boundary then E has the least upper bound This property of ℝ is very plausible geometrically. If the set E lies entirely to the left of some number M , then you can imagine decreasing the value of M steadily until any further decrease causes M to be less than some point of E. At this point, sup E has been reached. The set E is indicated by bold green lines.

58. [Completeness Property] Give an example of a set of rationals that shows that { ~rationals } don't have a Completeness Property.

    { ~all rats < √2 } And there is no least rational number greater than √2. So the set has an upper bound but no least upper bound. Hence the rationals lack the Completeness Property.By contrast, the continuum “morally ought” to have the Completeness Property. We do not just want √2 to be a real number; we want to fill all the “gaps” in the rational line. Indeed, we want the continuum itself to have no “gaps” in it. That is just what we will get via Completeness.

59. [Completeness Property] Why is the Completeness Property of ℝ called so?

    Completeness = completes all the gaps. Intuitively, completeness implies that there are not any "gaps" (in Dedekind's terminology) or "missing points" in the real number line. This contrasts with the rational numbers, whose corresponding number line has a "gap" at each irrational value. In the decimal number system, completeness is equivalent to the statement that any infinite string of decimal digits is actually a decimal representation for some real number.

60. [Dedekind cut] Visually imagine a Dedekind cut.

    A Dedekind cut is a partition of the rational numbers into two sets A and B, such that all elements of A are less than all elements of B, and A contains no greatest element.

61. [Arithmetization] Visually imagine how to go: from rationals (ℚ) to reals (ℝ).