I think the question is translated ambiguously... what set of integers are we taking a permutation of, and how large is the integer grid? >.>

@above: presumably the problem means the following. matinyousefi wrote: Does there exist a bijection $f : \mathbb{Z}^2 \to \mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom?

Let me prove this version. popcorn1 wrote: Does there exist a bijection $f\colon\mathbb{Z}^2 \to \mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom? The answer is affirmative. First we prove an easy lemma. Lemma 1. Let $S\subseteq\mathbb Z$ be a subset which is unbounded in both directions. Then there exists an order-preserving bijection from $\mathbb Z $ to $S$. Proof. Let our desired function be $h$. We construct $h$ inductively. Let $h(0)$ be an arbitrary element of $S$. Assume $n$ is a nonnegative integer and $h$ is defined on $[-n,n]$. Define $h(n+1)$ to be the smallest element of $S$ which is larger than $h(n)$ and define $h(-n-1)$ to be the largest element of $S$ which is smaller than $h(n)$. Then $h$ is defined on $[-n-1,n+1]$. By construction, $h$ is a bijection and order-preserving. $\square$ The next lemma reduces a problem to a weaker case. Lemma 2. Assume there exists an injective function $g\colon\mathbb{Z}^2\to\mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. Then there exists a bijection $f\colon\mathbb{Z}^2 \to \mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. Proof. Set $S=\mathrm{im}(g)$. Each row (for instance the image of the horizontal line $y=0$) is already unbounded in both directions, and so is $S$. Let $h:\mathbb Z\to S$ be an order-preserving bijection. Then $f:=h^{-1}\circ g$ satisfies the requirements of the lemma. $\square$ Now we construct an injective function $g\colon\mathbb{Z}^2\to\mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. We construct $g$ inductively. Begin with $g(0,0)=0$. At each step, the domain of $g$ is a rectangular grid with finite dimensions, each row is increasing from left to right and each column increasing from top to bottom. The idea is that we can add a column or a row from any direction so that the conditions of $g$ are preserved. For example, let us show that we can add a row to the right. For this objective, we add an increasing column from top to bottom whose elements are all larger than the current elements of the rectangle. The other proofs are similar. This way, we can extend the rectangle indefinitely in all four directions and eventually reach a function on $\mathbb Z^2$.

math90 wrote: Let me prove this version. popcorn1 wrote: Does there exist a bijection $f\colon\mathbb{Z}^2 \to \mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom? The answer is affirmative. First we prove an easy lemma. Lemma 1. Let $S\subseteq\mathbb Z$ be a subset which is unbounded in both directions. Then there exists an order-preserving bijection from $\mathbb Z $ to $S$. Proof. Let our desired function be $h$. We construct $h$ inductively. Let $h(0)$ be an arbitrary element of $S$. Assume $n$ is a nonnegative integer and $h$ is defined on $[-n,n]$. Define $h(n+1)$ to be the smallest element of $S$ which is larger than $h(n)$ and define $h(-n-1)$ to be the largest element of $S$ which is smaller than $h(n)$. Then $h$ is defined on $[-n-1,n+1]$. By construction, $h$ is a bijection and order-preserving. $\square$ The next lemma reduces a problem to a weaker case. Lemma 2. Assume there exists an injective function $g\colon\mathbb{Z}^2\to\mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. Then there exists a bijection $f\colon\mathbb{Z}^2 \to \mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. Proof. Set $S=\mathrm{im}(g)$. Each row (for instance the image of the horizontal line $y=0$) is already unbounded in both directions, and so is $S$. Let $h:\mathbb Z\to S$ be an order-preserving bijection. Then $f:=h^{-1}\circ g$ satisfies the requirements of the lemma. $\square$ Now we construct an injective function $g\colon\mathbb{Z}^2\to\mathbb{Z}$ such that each row is increasing from left to right and each column increasing from top to bottom. We construct $g$ inductively. Begin with $g(0,0)=0$. At each step, the domain of $g$ is a rectangular grid with finite dimensions, each row is increasing from left to right and each column increasing from top to bottom. The idea is that we can add a column or a row from any direction so that the conditions of $g$ are preserved. For example, let us show that we can add a row to the right. For this objective, we add an increasing column from top to bottom whose elements are all larger than the current elements of the rectangle. The other proofs are similar. This way, we can extend the rectangle indefinitely in all four directions and eventually reach a function on $\mathbb Z^2$. great solution but how can you come up the idea ?

I have seen many problems which involve inductive construction, so that the function is eventually "implicit". The idea of inductive construction is defining the elements one by one, so that you extend the information given "a little" information, usually finite. In this example, I chose rectangle because the requirement of increasing sequence is much easier to control. After some investigation, I realized that if we require only "injective" then the problem is much easier. Then I came up with lemma 1. Here are two examples of this type which I recalled.

Example 1

Example 2

math90 wrote: I have seen many problems which involve inductive construction, so that the function is eventually "implicit". The idea of inductive construction is defining the elements one by one, so that you extend the information given "a little" information, usually finite. In this example, I chose rectangle because the requirement of increasing sequence is much easier to control. After some investigation, I realized that if we require only "injective" then the problem is much easier. Then I came up with lemma 1. Here are two examples of this type which I recalled.

Example 1

Example 2

Okay, if you have time, can you post those problem's solution ?