Countability of Set of Lines Passing Through Two Integer Points

[milena24]

Homework Statement

I have to prove the countability of the set of all lines on the Euclidean plane passing through at least two points whose coordinates are both integers.

Homework Equations

Proofs don't have particular equations (at least that's what my book says)

The Attempt at a Solution

First thing I did was, in all honesty, try to figure out the actual basis of the Euclidean plane.
This yielded that it is the set of all ordered pairs of real numbers, with n-tuples considered vectors with n-components. This would translate to $$\Re^{2}$$

Now my interpretation of the question is that the given about passing through at least two points with integer coordinates doesn't tell me much as it to actually be a line it would also need to pass through non-Integer coordinates, regardless of how the lines are arranged. Furthermore, I believe any line with a slope will at some point from -$$\infty$$ $$\infty$$ cross at least two points that have integer coordinates, again, excluding vertical or horizontal lines.

This makes considering $$\Re$$ $$\times$$ $$\Re$$ vs Z $$\times$$ Z a bit difficult to understand. I find it rather vague right now...

Now, if I want to prove it's not countable by trying to prove it is, I end up with trying to prove it's bijective... as it's the only thing that has been covered in class...

f: N $$\rightarrow$$ $$\Re^{2}$$, but I feel the right side is always going to grow faster, so it is unlikely to be onto, I hypothesize uncountable.

now, looking at the question, it doesn't seem to care about the points in between as long as the condition is met for it to pass through two points with integer coordinates, so is we just want to count lines, would it be valid to just take, say y = mx + b for each feasible combination, meaning I'm actually proving I can count the input-outputs of that equation?
Would that mean that given that case it would be countable because ever input x will produce a single y? This would still be uncountable in my opinion, given the case of the horizontal line not ever being one to one...I'm kinda stumped with the question, and I guess I'm too tangled up to understand what I need to do here. Please help... at least a kickstart would suffice...

 

[hgfalling]

Not all lines satisfy the requirement.

For example, the line $y = \sqrt{3}x$ does not. Do you see why?

Now, consider the properties of the set of lines that DO intersect two points in Z x Z. As you say, they are almost all of the form y = mx + b. (except for the vertical ones, which you can treat separately). What (m,b) pairs satisfy the requirement?

Then you probably have a proof.

 

[milena24]

Ok i see why that line wouldn't conform... because it would take a irrational x to get an integer y... so basically, that would mean I need the slope to be a rational, also, B would have to be a rational for it to work...

so basically the ordered pair must both be of the same type... is m is integer, must be integer. if m is rational, b must be rational. Would it suffice to say m,b $$\in$$ Q?

Also... how do i even treat vertical lines?
The set of vertical lines where we can have an integer in both coordinates would be onto, yes, but I cannot see a case where it would ever be one-to-one, x=0 yields a range of y = {1,2,3,...}

so bijection would not allow vertical lines to be countable, so given this subset of my lines is not countable because it isn't bijective, did I just prove it is uncountable? or am I missing the bijection part of the definition?

So, I guess my confusion is... would ZxZ be a subset of R^2?

Also... is this even a valid proof?
How do I write out a proof without using mathematical theorems? or am I supposed to use the theorems.

I haven't seen proofs since middle school geometry, so please bear with me.

So this is what I know now:
- Lines must conform to the point-slope form, y=mx+b, whose possible ordered pairs for x,y are determined by the cartesian product ZxZ, given x and y must be integers.
- Also, given x,y must be integers, this is only satisfied if m and b are rational numbers
- Verticals and horizontals are not bijective...

so I guess my confusion here is am I proving I can count all the possible values for m,b that satisy these requirements? If so, since these are essentially a cartesian product of rational numbers, and rational numbers are countable, i have just proved the statement is true, as the set is countable?

If so, and there is nothing missing from the above...how do I represent this?
I have the concept... I just really don't get how to write it out for such a specific scenario...
all that comes to mind is:

for all m,b in QxQ, there exists f(m,b) = mx + b such that (x, f(m,b)) $$\in$$ ZxZ but that doesn't look right...

 

[Dick]

Don't worry about the point slope form. Every distinct pair of points has exactly one line going through it. The distinct points are a subset of (ZxZ)^2 however you chose to organize them. If you know (ZxZ)^2 is countable then you know any subset is countable. Don't get caught up in the details.

 

[milena24]

Yeah, I don't want to, the problem is that I have to use notation for the class, so I am trying to write it out in a non-paragraph form, so that's why I'm a bit mized up in how to write the opening statement... the construction step

 

[Dick]

But it DOESN'T MATTER. To say the number is (ZxZ)^2 is clearly 'overcounting'. Some pairs don't correspond to lines if they are identical. Other pairs in (ZxZ)^2 correspond the same line. So the number of distinct lines must be a subset of (ZxZ)^2. You don't need a bijection to prove a number is countable. If A is a surjection onto B, then the cardinality of A is >= B.

 

[milena24]

hmm... i see what you mean... but given the specific scenario... wouldn't it be (QxQ)x(ZxZ)?
i might be missing the point of the (ZxZ)^2...

are we saying the set of lines conforming to (ZxZ)^2 is a surjection on N, thus making it uncountable? I am so confused now...

 

[Dick]

hmm... i see what you mean... but given the specific scenario... wouldn't it be (QxQ)x(ZxZ)?
i might be missing the point of the (ZxZ)^2...

are we saying the set of lines conforming to (ZxZ)^2 is a surjection on N, thus making it uncountable? I am so confused now...

The problem statement says 'all lines on the Euclidean plane passing through at least two points whose coordinates are both integers'. A point whose coordinates are integers can be identified with an element of ZxZ. A pair of points is in (ZxZ)x(ZxZ) or (ZxZ)^2. If you know (ZxZ)^2 is countable, than any subset is countable, right? Any element of the subset of (ZxZ)^2 in which the two points aren't equal maps to a unique line, right? Isn't this a surjection from a subset of (ZxZ)^2 onto the set of lines?

 

[milena24]

ah, i get it now!

so what we're saying is that since (ZxZ)^2 is countable, and all of its subsets are countable, the subsets corresponding to the rule that (ZxZ)$$_{1}$$ $$\neq$$ (ZxZ)$$_{2}$$ are surjective onto the set of all lines, hence the et of lines is also countable.

Is that right?


Those were supposed to be subscript, not superscript :S

 

[Dick]

ah, i get it now!

so what we're saying is that since (ZxZ)^2 is countable, and all of its subsets are countable, the subsets corresponding to the rule that (ZxZ)$$_{1}$$ $$\neq$$ (ZxZ)$$_{2}$$ are surjective onto the set of all lines, hence the et of lines is also countable.

Is that right?


Those were supposed to be subscript, not superscript :S

That's the idea. I don't like the notation (ZxZ)$$_{1}$$ $$\neq$$ (ZxZ)$$_{2}$$ much though. Sometimes it's much more clear to express yourself using words.

 

[milena24]

Yeah, i wold use words, but this professor likes the function notation and writing out each step as so.

so I'm going to have to do like f: (ZxZ)^2 -> N, and prove it so on...

Would that be the correct start?

Then i would need to proceed to defining a restriction where (ZxZ)_1 doesn't equal (ZxZ)_2 as that would not form a line. Then i'd say ZxZ is countable by definition that the cross-product of two countable sets are countable... then (ZxZ)x(ZxZ) would also follow that norm.

Then... i'd have to state that there is one and only one line going through each tuple resulting from (ZxZ)x(ZxZ), as long as the aforementioned restriction is met, so the subsets conforming to it is surjective to the set of all possible lines, and hence the set of lines that cross at least two points with integer coordinates are countable...Is that logic sound?

 

[Dick]

I would express your restriction by just saying if (a,b) is an element of (ZxZ)x(ZxZ), i.e. a and b are elements of ZxZ, restrict to the set A such that a is not equal to b. Now you have a surjection of A onto the set of all lines passing through two integer points. Did you mean N to mean the set of such lines? Don't get stuck trying to find fancy looking (but confusing) notation to express what you mean. I'm sure that's not what your professor wants. Use words if it's clearer. Your logic is sound. Just try and express it clearly.