4 fixed second proof

The following theorem has several essentially different proofs that need quite different levels of mathematical background, ranging from high school to graduate level. Which proof is most natural depends on who you ask, but many people (including me) will find at least some proof unnecessarily complicated.

There exists a set $A$ that is everywhere dense on the square $[0, 1]^2$, but such that for any real number $x$, the intersections $A \cap (\{x\} \times [0, 1])$ and $A \cap ([0, 1] \times \{x\})$ are both finite.

(This is a variant of a homework problem posed by Sági Gábor.)

Here's the idea of a few proofs.

• $A = \{(p/r, q/r) \mid p, q, r \in \mathbb{Z} \text{ and } \gcd(p,r) = \gcd(q,r) = 1 \}$ is dense because if you subdivide the square to $2^n$ times $2^n$ squares, $A$ contains the center of each square; and has only as many points on each horizontal or vertical line as the denominator of $x$.

• $A = \{(x + y\sqrt3, y - x\sqrt3) \mid x, y\in\mathbb{Q} \}$ is dense because it's a scaled rotation of $\mathbb{Q}^2$, but has at most one point on every horizontal or vertical line otherwise $\sqrt3$ would be irrationalrational.

• Choose $a_0, b_0, a_1, b_1$ as four reals linear independent over rationals, this is possible because of cardinalities. $A = \{(ma_0 + na_1, mb_0 + nb_1) \mid m, n \in \mathbb{Q}\}$ has no two points sharing coordinates because of rational independence, and $A$ is dense because it's a non-singular affine image of $\mathbb{Q}^2$.

• A is the set of a countably infinite sequence of random points independent and uniform on the square. This is almost surely dense, but almost surely has no two points that share a coordinate.

• Choose a countable topological base of the square, then choose a point from each of its elements inductively such that you never choose a point that shares a coordinate with any point chosen previously.

• Choose a continuum (or smaller) size topological base of the square, then choose a point from each by transfinite induction such that when you choose a point, the cardinality of points chosen previously is less than continuum, thus you can avoid sharing coordinates with those points.

• Choose $a, b$ as reals such that $a, b, 1$ are linear independent over rationals, possible because of cardinalities. Let $A = \{((ma + nb) \bmod 1, (ma - nb) \bmod 1) \mid m, n \in \mathbb{Z}\}$. No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A is closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by $\pi/2$, it's also dense on the rotation of that line, thus, because it's closed to addition, dense everywhere.

• Choose $a, b$ like above. Let $A = \{(an \bmod 1, bn \bmod 1) \mid n \in \mathbb{Z}\}$. Prove A is dense by ergodic theory and Fourier analysis.

Update: Edited the drafts of proofs to somewhat cleaner. Permuted proofs. Also fixed typo in last proof.

3 copyedit proofs, permute them
• Choose $a_0, b_0, a_1, b_1$ as four reals linear independent over rationals, this is possible because of cardinalities. $A = \{(mx_0 {(ma_0 + nx_1na_1, my_0 mb_0 + ny_1nb_1) \mid m, n \in \mathbb{Q}\}$ where $x_0, y_0, x_1, y_1$are rational independent, which is possible because of cardinalities. No has no two points share sharing coordinates because of rational independence, and $A$ is dense because it's the a non-singular affine image of $\mathbb{Q}^2$.

• $ • A= \{((mx + ny) \bmod 1, (my - nx) \bmod 1) \mid m, n \in \mathbb{Z}\}$ where $x, y, 1$ are rational independent, which is possible because of cardinalities. No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by 90 degrees, it's also dense everywhere.

• A is the set of a countably infinite sequence of random points independent and uniform on the square. This is almost surely dense, but almost surely has no two points that share a coordinate.

• Choose a continuum (or smaller) size topological base of the square, then choose a point from each by transfinite induction such that when you choose a point, the cardinality of points chosen previously is less than continuum, thus you can avoid sharing coordinates with those points.

• Choose $a, b$ as reals such that $a, b, 1$ are linear independent over rationals, possible because of cardinalities. Let $A = \{(nx {((ma + nb) \bmod 1, ny (ma - nb) \bmod 1) \mid m, n \in \mathbb{Z}\}$ where . No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A is closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by $x\pi/2$, yit's also dense on the rotation of that line, thus, because it's closed to addition, dense everywhere.

• Choose $a, b$ like above. Let $A = \{(an \bmod 1, bn \bmod 1) \mid n \in \mathbb{Z}\}$are rational independent. Prove A is dense by ergodic theory and Fourier analysis.

• Update: Edited the drafts of proofs to somewhat cleaner. Permuted proofs. Also fixed typo in last proof.

2 fix spacing of formulas

The following theorem has several essentially different proofs that need quite different levels of mathematical background, ranging from high school to graduate level. Which proof is most natural depends on who you ask, but many people (including me) will find at least some proof unnecessarily complicated.

There exists a set $A$ that is everywhere dense on the square $[0, 1]^2$, but such that for any real number $x$, the intersections $A \cap (\{x\} \times [0, 1])$ and $A \cap ([0, 1] \times \{x\})$ are both finite.

(This is a variant of a homework problem posed by Sági Gábor.)

Here's the idea of a few proofs.

• $A = \{(p/r, q/r) | \mid p, q, r \in \mathbb{Z} \text{ and } \gcd(p,r) = \gcd(q,r) = 1 \}$ is dense because if you subdivide the square to $2^n$ times $2^n$ squares, $A$ contains the center of each square; and has only as many points on each horizontal or vertical line as the denominator of $x$.

• $A = \{(x + y\sqrt3, y - x\sqrt3) | \mid x, y\in\mathbb{Q} \}$ is dense because it's a scaled rotation of $\mathbb{Q}^2$, but has at most one point on every horizontal or vertical line otherwise $\sqrt3$ would be irrational.

• $A = \{(mx_0 + nx_1, my_0 + ny_1) | \mid m, n \in \mathbb{Q}\}$ where $x_0, y_0, x_1, y_1$ are rational independent, which is possible because of cardinalities. No two points share coordinates because of rational independence, and $A$ is dense because it's the a non-singular affine image of $\mathbb{Q}^2$.

• $A = \{((mx + ny) \bmod 1, (my - nx) \bmod 1) | \mid m, n \in \mathbb{Z}\}$ where $x, y, 1$ are rational independent, which is possible because of cardinalities. No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by 90 degrees, it's also dense everywhere.

• A is the set of a countably infinite sequence of random points independent and uniform on the square. This is almost surely dense, but almost surely has no two points that share a coordinate.

• Choose a countable topological base of the square, then choose a point from each of its elements inductively such that you never choose a point that shares a coordinate with any point chosen previously.

• Choose a continuum (or smaller) size topological base of the square, then choose a point from each by transfinite induction such that when you choose a point, the cardinality of points chosen previously is less than continuum, thus you can avoid sharing coordinates with those points.

• $A = \{(nx \bmod 1, ny \bmod 1) | \mid n \in \mathbb{Z}\}$ where $x, y, 1$ are rational independent. Prove A is dense by ergodic theory and Fourier analysis.

1 [made Community Wiki]