Recall that the VC dimension of a hypothesis class is the largest set of points that can be shattered by the class. Start by considering small sets of points (e.g., 2, 3, or 4 points) and determine whether axis-aligned rectangles can shatter them.

For a set of points to be shattered by axis-aligned rectangles, every possible labeling of the points (i.e., every possible subset of points) must be realizable by some axis-aligned rectangle. Try to construct such labelings for a set of 4 points arranged in a grid (e.g., the corners of a square).

To prove that the VC dimension is 4, you must show that (a) axis-aligned rectangles can shatter any set of 4 points, and (b) they cannot shatter any set of 5 points. For part (b), consider a set of 5 points where no 4 points are in convex position (e.g., 4 points forming a square and a fifth point inside the square). Show that it is impossible to realize certain labelings with axis-aligned rectangles.