0
$\begingroup$

Suppose we define "finite set" as a set on which there can exist a cyclic path that passes through all of its elements. (The details of the formulation are present below).

I have two questions:

  1. Is the above definition equivalent to a known definition of "finite set"?
  2. If the answer to 1. is yes, then to which of these known definitions it is equivalent?

Formal workup:

Define: $ P \text { is a path on S} \iff \forall m \in P [\exists k,l \in S [m=(k,l)]] \\ \wedge \forall y\in S [\exists k [(y,k) \in P \lor (k,y) \in P]] \\ \wedge \forall s [\exists k ((s,k) \in P) \implies \exists! k ((s,k) \in P )] \\ \wedge \forall s [\exists k ((k,s) \in P) \implies \exists! k ((k,s) \in P )] \\ \wedge \exists z \forall s ([\exists k ((s,k) \in P) \wedge \not \exists r ((r,s) \in P)] \implies s=z) \\ \wedge \exists z \forall s ([\exists k ((k,s) \in P) \wedge \not\exists r ((s,r) \in P)] \implies s=z) $

Define: $P \text { is a path} \iff \exists S (P \text{ is a path on S})$

Define: $x \text { is a point on } P \iff \exists S (P \text { is a path on S} \wedge x \in S)$

Define: $x \text { is an end point on } P \iff x \text { is a point on } P \\ \wedge \exists!m \in P (\exists k [m=(x,k)] \lor \exists l [m=(l,x)])$

Define: $ P \text { is an endless path on } S \iff P \text{ is a path on } S \\ \wedge \not \exists x (x \text { is an end point on } P)$

Define: $ Q \text { subpath } P \iff P \text { is a path } \wedge Q \text { is a path } \wedge Q \subset P $

Define: $ P \text { is a continuous path} \iff P \text { is a path } \\ \wedge \forall Q,T,A,B (Q\neq \emptyset \wedge T\neq \emptyset \wedge Q \text { is a path on } A \wedge T \text { is a path on } B \wedge Q \text { disjoint } T \wedge (Q \cup T) \text{ subpath } P \implies \neg (A \text{ disjoint } B))$

Define: $ P \text { is a cyclic path on } S \iff P \text { is an endlesss path on S } \wedge P \text { is a continuous path}$

Define: $ \text { set S is finite} \iff \exists P (P \text { is a cyclic path on S})$

What I like about this definition is that it doesn't mention the naturals, it doesn't mention well foundedness or well-ordered relations in an explicit manner, it depends on "endlessness", which goes in the opposite direction to the common notion of the finite set as a set that has every subset of it having two ends, so it looks different from the common known definitions of the finite, on the other hand it does depict the point of failure of finiteness in the non-standard naturals, we can have a $\mathbb{Z}$-chain that can go unnoticed if we cannot see all sub-paths on a set, so a really infinite set can be disguised as finite. Although it appears trivial (and I had already knew half of the answer to it), yet still I think that confirming its equivalence with the known definitions of finite set is a relevant issue, especially in theories where separation fails like $NF$ and the alike.

$\endgroup$
5
  • $\begingroup$ Could you clarify: why doesn't $\mathbb{Z}$ have a cyclic path, according to your definition? That is, unless I have misunderstood, it seems to me that a $\mathbb{Z}$-chain is endless and continuous. $\endgroup$ Commented Dec 31, 2017 at 13:51
  • $\begingroup$ @Joel David Hamkins, The set $ Q= \{(n,n+1)| n \in N \wedge n>=3\}$ is a path on the set $A=N \setminus \{0,1,2\}$, and the set $T=\{(-n, -n+1)| n \in N \wedge n>=1\}$ is a path on the set $B= Z \setminus Z^+$, and yet $Q \cup T$ is a subpath of $Z$ however we have $A$ disjoint $B$. $\endgroup$ Commented Dec 31, 2017 at 16:31
  • $\begingroup$ Just to correct my last comment I meant that $Q \cup T$ is a subpath of the $+1$ chain on $Z$ (which is $\{(n,n+1)| n \in Z\}$). It would have been easier if we defined finite set as a set where there exist an endless path defined on it and such that every endless path defined on it being cyclic, but I think this could be proved. $\endgroup$ Commented Dec 31, 2017 at 17:03
  • $\begingroup$ In your definition of P is a path on S, I believe that the second clause is not expressing what you intend, since you are saying that there is a unique $m$ of the one kind or there is a unique $m$ of the other kind. But I think what you want to say is that there is at most one $m$ of each kind. That is, you don't want to allow that $P$ has many edges coming out of $y$, as long as there is a unique edge coming into $y$, right? $\endgroup$ Commented Jan 3, 2018 at 2:19
  • $\begingroup$ right, I've fixed it. $\endgroup$ Commented Jan 3, 2018 at 12:48

1 Answer 1

0
$\begingroup$

It seems to me that your definition is equivalent to the usual definition of finite set in set theory (a set is finite if it has $n$ elements for some natural number $n$).

It is clear that any finite set satisfies your definition, since we can easily build cycles on an $n$-element set.

Conversely, if we have such a cyclic path on a set $S$ as you describe, then fix any element $b\in S$, to be used as a base point. We can define the point that is distance $n$ from $b$ in each direction. If there are points at every distance, then we get a $\mathbb{Z}$-chain and we can violate the cycle property as you did in the comments. So the points must all be at bounded finite distance, and in this case we can find a bijection with a natural number.

$\endgroup$
7
  • $\begingroup$ I actually asked this question because it has been claimed in the following website that a definition which is based on crossely a similar intuitive line of thought is equivalent to Dedekind. It is present here: dcproof.com/Infinity.html $\endgroup$ Commented Jan 2, 2018 at 22:38
  • $\begingroup$ actually, he claims he has an automated proof of that, present here: dcproof.com/EquivalentFinites-v2.htm $\endgroup$ Commented Jan 2, 2018 at 22:41
  • $\begingroup$ On the site you mention, he is claiming the equivalence of two formulations of Dedekind finite, namely, a set has no countably infinite subset if and only if every self-injection is surjective. That is correct. $\endgroup$ Commented Jan 3, 2018 at 2:21
  • $\begingroup$ Ok, thanks. I see now. I wonder if there are conditions where this definition departs from the known definition of the finite set. $\endgroup$ Commented Jan 3, 2018 at 13:07
  • $\begingroup$ @Zuhair If "this definition" means either definition of Dedekind finite, then yes, it sometimes departs from the standard definition of finiteness. Among many examples are the Basic Fraenkel Model and the Basic CohenModel, as described in Jech's book "The Axiom of Choice". On the other hand, if "this definition" means the one in your question, then it does not depart from the standard definition of finiteness, as Joel explains in this answer. $\endgroup$ Commented Jan 3, 2018 at 22:16

Not the answer you're looking for? Browse other questions tagged .