5
$\begingroup$

Walter Rudin's Principles of Mathematical Analysis, page 25 has this definition:

For any postive integer $n$, let $J_n$ be the set whose elements are the integers $1,2,\ldots,n$.

$A$ is finite if $A\sim J_n$ for some $n$ (the empty set is also considered to be finite)

Here $B\sim C$ means ``there exists a 1-1 mapping of $B$ onto $C$''.

Wikipedia has the same definition:

Formally, a set $S$ is called finite if there exists a bijection $f:S\rightarrow\{1,\ldots,n\}$ for some natural number $n$.

Question: is it not sufficient to stipulate that the map be 1-1? Requiring also that the map be onto seems to be unnecessary, and it seems like best practice to make minimal definitions.

$\endgroup$
15
  • 6
    $\begingroup$ You are absolutely correct, it is only necessary to require that it is 1-1. But I am not sure whether it is the "best practice" to use minimal definitions, it would make proving theorems a little harder... $\endgroup$
    – Yanko
    Aug 19 at 22:09
  • 1
    $\begingroup$ Well that would work :-). It is a convention, I see your point but I also see why some people would prefer to avoid using a proposition over and over, it is a matter of taste so no point arguing about it haha $\endgroup$
    – Yanko
    Aug 19 at 22:17
  • 4
    $\begingroup$ Sometimes minimal definitions are not the simplest or the easiest. Saying a finite set one in which there is a bijection between $\{1,....,n\}$ and it is both formally valid and it is intuitive (it basically says you can count that it has $n$ elements). Although saying that an injection that need not be surjective from $S$ to $1,....n$ is for less intuiitive and is not as simple and there is no longer any concept of "how many elements does it have". $\endgroup$
    – fleablood
    Aug 19 at 22:31
  • 2
    $\begingroup$ To further illustrate @user14111’s point, we could define a group as a pair $(G, \cdot)$, where (1) $\cdot$ is associative, and there is some $e \in G$ such that (2) $e$ is a right identity - $\forall x \in G (x \cdot e = x)$, and (3) right inverses exist - $\forall x \in G \exists y \in G (x \cdot y = e)$. See math.stackexchange.com/q/65239. This definition is shorter than the usual definition - defining $e$ to be a 2-sided identity and having 2-sided inverses - but I would certainly not argue it’s a better definition. $\endgroup$ Aug 20 at 1:03
  • 2
    $\begingroup$ It might be considered even "simpler" to say "A set $S$ is infinite if an injective function from $\mathbb{N}$ to $S$ exists. A set is finite if it is not infinite." No need for the choice of $J_n$ set at all. $\endgroup$
    – aschepler
    Aug 20 at 2:04

1 Answer 1

6
$\begingroup$

If you accept classical logic, you can show that if there is some injective $f : S \to \{1, \ldots, n\}$, then $S$ is finite. Equivalently, every subset of a finite set is finite. However, if you do not accept classical logic, you cannot prove this.

By “classical logic”, I mean the principle that for all propositions $P$, $P \lor \neg P$. This principle is equivalent to a few others, like double negation elimination, proof by contrapositive, etc. Logic formulated without these principles is known as “constructive logic”.

It turns out that “every subset of a finite set is finite” is equivalent to classical logic. To see this, consider a proposition $P$. Then take the set $S = \{1 \mid P\}$. That is, $\forall x (x \in S \iff x = 1 \land P)$.

Clearly, $S$ is a subset of the finite set $\{1\}$, which is finite since it is in bijection with itself. Suppose $S$ is finite; take some $n$ such that there is a bijection $S \cong \{1, \ldots, n\}$.

Because $n$ is a natural number, we know it is either zero, or at least 1. If $n$ is zero, then $S$ is empty; therefore, $\neg P$. And if $n$ is at least one, then there is some $x \in S$, meaning that $P$ holds. So we have established $P \lor \neg P$.

However, the following can be shown constructively:

Consider $S \subseteq R$ where $R$ is finite, and suppose $\forall r \in R (r \in S \lor r \notin S)$. Then $S$ is finite.

Of course, with classical logic, the premise $\forall r \in R (r \in S \lor r \notin S)$ is automatically true. So classically, every subset of a finite set is finite.

One final point. There are a few reasons to be interested in constructive logic. The first is philosophical. Perhaps you don’t really believe $P \lor \neg P$ unless you know which one - $P$ or $\neg P$ - holds. Or perhaps you are a devotee of Brouwer and hold to some of his (admittedly strange) philosophical considerations about the nature of sequences and free choice.

But even if you strongly believe in classical logic, constructive logic is still incredibly useful. For example, any function $\mathbb{R} \to \mathbb{R}$ which can be defined constructively can also be constructively proved to be continuous. Similarly, if we can prove any proposition of the form $\forall n \in \mathbb{N} \exists m \in \mathbb{N} (P(n, m))$ constructively, then there exists some computable function $f : \mathbb{N} \to \mathbb{N}$ such that we can constructively prove $\forall n \in \mathbb{N} (P(n, f(n)))$.

Constructive logic has many other applications, especially in algebraic geometry and topos theory. You don’t have to believe in it (or more precisely, to disbelieve in classical logic) to make full use of its fruits.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.