1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Arrange N into a two-dimensional array

  1. Aug 20, 2016 #1
    1. The problem statement, all variables and given/known data
    The problem is to show that arranging N into the two dimensional array:
    [tex]
    \begin{matrix}
    1 & 3 & 6 & 10 & ... \\
    2& 5& 9& ... \\
    4& 8& & \\
    7&... & & \\
    ...
    \end{matrix}
    [/tex]

    leads to a proof that the union of an infinite number of countably infinite sets is countable.
    2. Relevant equations
    none

    3. The attempt at a solution
    Let xij be the ith element of the jth row of the array. Let n1j be the minimum of Aj, let n2j be the next smallest element of Aj, and so on. Then define the function given by nij ↔ xij, which assigns the ith smallest element of Aj to the ith element of the jth row. It is clear that this function is bijective. Since {nij} = ∪n=1An and {xij} = N, we therefore have a bijection between n=1An and N, and therefore the infinite union is countable.
     
  2. jcsd
  3. Aug 21, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your approach is a little confusing. You use the symbol ##A_j## but do not say what it is. You then set out to define a function but the bidirectional arrow ##\leftrightarrow## leaves us wondering which way the function goes, and it does not tell us what the domain and range are. We can say nothing about whether a function is bijective unless we know its domain and range.

    The classical, and clearest, way to define a function ##f## is to write something like:

    'define the function ##f:D\to R## such that ##f(x)=##<formula specifying the result of applying the function to ##x##>'​

    This tells us that ##f, D## and ##R## are the function's name, domain and range respectively, and the 'such that' part then tells us what value is obtained by applying it to an arbitrary element of the domain.
     
  4. Aug 21, 2016 #3
    I am sorry, I should have been clearer.

    The sets ##A_j## refer to the countably infinite sets in the infinite union in the problem statement, that is, to prove that the union n=1An is countably infinite. All that is given about these sets is that they are countably infinite. I misunderstood the meaning of the bidirectional arrow.

    My approach is to show that there is a bijection between the infinite union and N. To do this, I use the fact that each row in the array represents a countably infinite subset of N, and that the set of all elements in the array is N. Then I would show that the function that assigns ##n_{ij}##, the ##i^{th}## smallest element in set ##A_j##, to ##x_{ij}##, the ##i^{th}## element of ##R_j##, the ##j^{th}## row in the array, is a bijection. [

    So does that mean that I would say that I am defining a function ##f: A_j \rightarrow R_j##?
     
  5. Aug 21, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I suggest you start by defining a bijective function from ##\mathbb N## to points in the number lattice you have drawn, where a point in the lattice is represented by a pair of integer coordinates that are the row and column number.

    Also, you can't define ##n_{1j}## to be the minimum of ##A_j## because to have a minimum, a set must be ordered, and the problem does not say the sets are ordered. Why not instead use the fact that we are told that each set ##A_j## is countable, which means that there exists at least one bijection ##f_j## between ##\mathbb N## and ##A_j##.
     
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: Arrange N into a two-dimensional array
Loading...