Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Help with set theory notation

  1. Jan 27, 2017 #1
    I bought a maths book and have discovered it's somewhat above my level.

    In particular I'm confused about one bit of notation. I understand the "is a member of" operator when it takes a set as argument (e.g. n ∈ ℝ) but not when the book uses it with functions (e.g. n ∈ f)

    Does n ∈ f mean that the number n can be returned by function f?
     
  2. jcsd
  3. Jan 27, 2017 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need to give more context. My guess is that a function can be seen as a set. For example, the function ##f(x) = x^2## can be seen as the set of points ##\lbrace (x, x^2): x \in \mathbb{R} \rbrace##, also commonly known as the graph of ##f##.

    In this case, you could use the notation: ##f = \lbrace (x, x^2): x \in \mathbb{R} \rbrace##.

    And, here, ##n \in f## would mean that ##n = (x, x^2)## for some real ##x##.
     
  4. Jan 27, 2017 #3

    fresh_42

    Staff: Mentor

    This is strange, not to say wrong. A function ##f\, : \,X \rightarrow Y## can be written as a subset ##f=\{(x,y)\,\vert \,y=f(x)\} \subseteq X \times Y## of the Cartesian product, but this cannot explain the notation ##n \in f## unless ##n## is a pair. Can you give some more context?
     
  5. Jan 27, 2017 #4

    fresh_42

    Staff: Mentor

  6. Jan 29, 2017 #5
    I've copied part of the book below:

    Theorem 2.2 There are infinite sets that are not enumerable.
    Proof Consider the powerset of N, in other words the collection P whose members are all the sets of numbers (so X ∈ P iff X ⊆ N).
    Suppose for reductio that there is a function f : N→P which enumerates P, and consider what we’ll call the diagonal set D ⊆ N such that n ∈ D iff n /∈ f(n).
    Since D ∈ P and f by hypothesis enumerates all the members of P, there must be some number d such that f(d) = D.
    So we have, for all numbers n, n ∈ f(d) iff n /∈ f(n). Hence in particular d ∈ f(d) iff d /∈ f(d). Contradiction!​
     
  7. Jan 29, 2017 #6

    pasmith

    User Avatar
    Homework Helper

    That's not what the text is saying.

    This is defining [itex]f[/itex] as a function from the natural numbers [itex]\mathbb{N}[/itex] to the collection [itex]P[/itex] of subsets of natural numbers. Thus if [itex]n \in \mathbb{N}[/itex] then [itex]f(n) \subset \mathbb{N}[/itex]. The statement [itex]n \in f(n)[/itex] is therefore perfectly sensible, since it always makes sense to ask if a particular natural number is or is not a member of a particular subset of the natural numbers.
     
  8. Jan 29, 2017 #7

    fresh_42

    Staff: Mentor

    O.k., but this is not what you wrote. ##n \in f## is something different to ##n \in f(n)## where ##f: \mathbb{N}\rightarrow \mathcal{P}(\mathbb{N})## is a function which values are sets ##X##, so ##n \in X=f(n) \in \mathcal{P}(\mathbb{N})## makes sense. This is not the same as ##n \in f \in \mathcal{P}( \mathbb{N} \times \mathbb{N})## which we explained in the previous posts.

    The theorem is proven by the so called diagonal argument. It is a formal notation of the following principle:

    We want to show, that the set of all subsets of ##\mathbb{N}## isn't enumerable.

    If we have an element ##X \in \mathcal{P}(\mathbb{N})##, i.e. a subset ##X \subseteq \mathbb{N}##, then we can write it down number by number: ##X= n_1n_2n_3n_4 \ldots##
    Now let's assume ##\mathcal{P}(\mathbb{N})## is enumerable. Then there would be a complete list like
    $$\begin{matrix} 1: &X_1 & = & n_{11}n_{12}n_{13} \ldots \\ 2: &X_2 & = & n_{21}n_{22}n_{23} \ldots \\ 3: & X_3 & = & n_{31}n_{32}n_{33} \ldots \\ &\vdots &&\\ \end{matrix}$$
    which contains all elements of ##\mathcal{P}(\mathbb{N})##, or subsets of ##\mathbb{N}##.
    The diagonal ##d## is now the number ##d=n_{11}n_{22}n_{33} \ldots## We next add ##+1## to all of the numbers ##n_{ii}\,##.
    Since by assumption we have enumerated all, this new number ##d'## (or subset ##d'=\{n_{11}+1,n_{22}+1,n_{33}+1, \ldots\}## if you like) has to occur somewhere, say ##d'=X_k##. However the ##k-##th position of ##d'## is ##n_{kk}## by enumeration of the ##X_i## and ##n_{kk}+1## by construction of ##d'##. This cannot both be true, which means there is no way to enumerate ##\mathcal{P}(\mathbb{N})##.

    You might want to read the proof in the book again and figure out, why both are basically the same. It is also the method used to show why ##[0,1]## or ##\mathbb{R}## are uncountable. Whether ##|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|## holds is called the continuum hypothesis. It cannot be deduced from the usual axioms of set theory, i.e. by the Zermelo-Fraenkel axioms (ZF). If you read ZFC somewhere, then Zermelo-Fraenkel + Contnuum hypothesis is meant. (Usually it is also assumed, if nothing is said.)
     
  9. Jan 29, 2017 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That is not the continuum hypothesis and it can be proven in ZFC.
     
  10. Jan 29, 2017 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    ZFC means Zermelo-Fraenkel with choice. Not the continuum hypothesis.
     
  11. Jan 29, 2017 #10
    Thanks. It's becoming clear now.

    Boggled by some of the unfamiliar notation and concepts, I was not appreciating the fact that the function f returns a set as its result, so the ∈ operator can of course be used on the outputs of f such as f (n).

    The book itself moves onto such diagonal proofs.
     
  12. Jan 29, 2017 #11

    fresh_42

    Staff: Mentor

    Thanks for clarification.
    Oops, I just had a quick look on Wiki to be sure, for I know I tend to forget where the "gap" really is, and only saw ##\mathfrak{c}=\aleph_1## and next ##2^{\aleph_0}=\aleph_1##. I should have read it with more care ... :sorry:
    Thanks for the corrections.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Help with set theory notation
Loading...