# Proper Negation

Gold Member
I thought this would be easy...

BEGIN QUOTE
Definition. If there exists a 1-1 mapping of A onto B... we write A~B. ...This relation... is called an equivalence relation.

Definition. For any positive integer n, Let J_n be the set whose elements are the integers 1, 2, ..., n; let J be the set consisting of all positive integers. For any set A we say:
a) A is "finite" if A~J_n for some n (the empty set is also considered to be finite).
b) A is "infinite" if A is not finite.
END QUOTE

I just want to define infinite by writing out the negation of a).
I wasn't sure if I had to change "some n", so I tried to rewrite a) using what FOL I know, but couldn't figure out how to combine all the requirements of the equivalence relation. I end up with several sentences. Is there a simpler way?
Ugh,
Rachel

Related Set Theory, Logic, Probability, Statistics News on Phys.org
matt grime
Homework Helper
Rewriting a) it states

A is finite if there exists an n such that A~J_n

the negation is (ie A is infinite if)

for all n A~/~J_n

where use ~/~ to mean does not inject to J_n

Gold Member
Thanks :)
So this excludes 'infinity' from being used as a positive integer... i.e. I can't start counting at infinity {n, n-1, n-2, ..., 1}. Just wanted to make sure.
Happy thoughts
Rachel

Just use the rules for the quantifiers:

$${\neg}({\forall}x)({\neg}{f})x=({\exists}x)fx$$

and

$${\neg}({\exists}x)f(x)=({\forall}x)({\neg}f)x$$

So, let $$A$$ be an arbitrary set, $$f$$ be the predicate "is finite", $$J_n$$ be the set of all natural numbers less than or equal to n, and $$XBY$$ be a bijection between two sets $$X$$ and $$Y$$.

So:
$${\exists}n:ABJ_n{\rightarrow}{fA}$$

Applying the negation:
$${\neg}{\exists}n:ABJ_n{\rightarrow}({\forall}n)({\neg}f)A}$$

matt grime
Homework Helper
infinity isn't a positive integer, and you're best off avoiding all use of infinity if you can. just use the adjective infinite. if no one used infinity (which is entirely possible and desirable) we'd all be much better off.

Why do you say that, Matt? I think infinity is a useful concept, despite its difficulties.

matt grime
Homework Helper
for the simple reason of the misunderstandings that arise, such as the one in this thread. Encouraging people to treat infinity as something physical (and i mean that in the same sense as 2, pi, e are physical numbers) only causes problems. I have no problems with people using it in compound names such as 'the point at infinity' or in phrases such as '1/x tends to infinity as x tends to zero', but many people misuse it to such an extent that I start to question its usefulness. even the otherwise admirable wolfram says infinity is 'something bigger than any natural number' which is a dangerous thing to say. In all those cases when we say infinity, we mean 'does not X finite Y' where X/Y could be "stop at some" /"number". It might be laborious to always say that but it would make it easier to deal with problems when they arise.

I've never personally encountered someone seriously involved in maths who misunderstood infinity in the manner you describe. But that's not much of an argument...

I think you're on to something when you point out that "Encouraging people to treat infinity as something physical (and i mean that in the same sense as 2, pi, e are physical numbers) only causes problems." My own thoughts are that it is dangerous to think of any number as such.

One position I've always had in regard to mathematical pedagogy is that teaching mathematics should also involve teaching the philosophy of mathematics. If more people had insight into these issues, then I think a lot of the conceptual difficulties with things like infinity (is there anything really like it, though? ;) ) wouldn't be as notable.

matt grime
Homework Helper
do a quick search for the number of posts here and on sci.math for people who don't understand why you can't divide 0 by zero or infinity by infinity and you'll see what you've to deal with in the "lay" person. to any reasonable mathematician the answer is 'well you can't because the axioms do not allow you to, and you may as well ask what the quotient of paint by alfred the great is.'

Gold Member
The whole point of my looking closer at this definition of an infinte set was to avoid a misunderstanding about infinity :) I was hoping it exculded infinity from being a number. I think it's telling that, of the two ideas
1) that you can start at 1 and, by repeated addition, end at infinity and
2) that you can start at infinity and, by repeated subtraction, end at 1,
though both must be equally incorrect, the error is much better hidden in the first than the second.
BTW where would be the best place to discuss infinity?
Happy thoughts
Rachel

matt grime
Homework Helper
The error in the second is just as obvious: infinity isn't an integer, it isn't a member of the real numbers, so you can't take anything away from it as it is not part of an algebraic system that you know about.

matt grime
Homework Helper
SOmething I meant to mention before. The property of A~B is not an equivalence relation. It is not symmetric

Gold Member
Great, now I have to ask. I understand 0/0 but what does this have to do with infinity/infinity? I thought infinity wasn't a number or is that the point?
Rachel

Gold Member
matt grime said:
The error in the second is just as obvious: infinity isn't an integer, it isn't a member of the real numbers, so you can't take anything away from it as it is not part of an algebraic system that you know about.
I meant the second was more obvious than the first. Have you never slipped and said "end at infinity" or seen other competent people slip?

matt grime
Homework Helper
a sloppy way of writig it is to say that 1/0=infinity, so that if we pretend this makes more sense is 0/0 = (0/1)*(1/0) = infinity/infinity.

Gold Member
matt grime said:
SOmething I meant to mention before. The property of A~B is not an equivalence relation. It is not symmetric
The quote is from Walter Rudin's 'Principles of Mathematical Analysis', 3rd ed. I omitted his definitions of "1-1 mapping" and "onto", but, as I understand them, "1-1"=injective and "onto"=surjective, making "~" bijective, though he doesn't use those terms. Do you want me to type out the two definitions, they aren't that long?
beginning of chapter 2, if you have it.

Last edited:
Gold Member
matt grime said:
a sloppy way of writig it is to say that 1/0=infinity, so that if we pretend this makes more sense is 0/0 = (0/1)*(1/0) = infinity/infinity.
So you kill two birds with one stone- infinity is undefined and n/0 is undefined- nice trick.

matt grime
Homework Helper
no you just needed to say the quote in full, as it stands it is in correct in your first post because you omit the mention of surjection, hence you imply that A~B if there is an injection is an equivlance relation. now that you've explained you've omitted the other part of the defintion I'm happy. note that you only need injections to decide if a set is finite or not.

Gold Member
He uses ~ to define countable and uncountable sets, I figure this is why he adds the "onto".

Only injections? I never thought of that. Is it because you cannot inject an infinite set into a finite set?

matt grime
Homework Helper
of course: if there is no injection there is certianly no bijection. moreover, if A injects to B and B injects to A then there is a bijeciton between them (schroeder bernstein)

Gold Member
I see. But I still haven't worked out a defintion using only injections. I'm stuck on the range of the function. The definition from above uses J_n={1, 2, 3, ..., n} as the finite set that A is injected into, but I want to define finite for any function on A- whose range needn't be the positive integers.
You can't define finite using only injections, so I must actually give a finite set, yes?
I'm stuck.
Rachel

Gold Member
B is finite if it will not inject into any of its proper subsets.?

matt grime
Homework Helper
the point is any finite set can be put in bijection with some J_n so you may replace the elements of the set with the numbers 1,2...,n or if you prefer you may label the elements x_1, x_2,..., x_n

you may define finite using only injections. set is finite if there is an injection into some J_n (and hence into infinitely many) and this implies it is in bijection with one of them (the least n). the proofs of those are left as an exercise for the reader.

no finite subset may inject into a proper subset of a finite set. do not think about the infinite case as this is a delicate set theoretic question (there is something called dedekind infinite, and this requires the axiom of choice to be true for it to be equivalent to the ordinary infinite, ie not finite, case. which needn't bother you here and now).

matt grime said:
no you just needed to say the quote in full, as it stands it is in correct in your first post because you omit the mention of surjection, hence you imply that A~B if there is an injection is an equivlance relation. now that you've explained you've omitted the other part of the defintion I'm happy. note that you only need injections to decide if a set is finite or not.
Umm, I noticed in the first post: "A onto B".

matt grime