2
$\begingroup$

let $A$ be a set such that for all $n \in $ N $ A ≉ N_n$ where $N_n = \{ 0 ,1 ,2 ...... n-1\} $

and $a$ be the Cardinality of $A$ meaning ($|A| = a$)

is it possible to prove that $a+1=a$ without using Axiom of choice ?

As a student who has just completed a basic course in set theory, I find it interesting that without the Axiom of Choice, a simple assertion like $a=a+1$ cannot be proven..

$\endgroup$
9
  • 7
    $\begingroup$ $a + 1 = a$ is usually called "$a$ is Dedekind-infinite" in choiceless contexts, whereas "$A$ is not in bijection with any finite set" is called "$a$ is infinite". You need some Choice to show "infinite implies Dedekind-infinite" - see Wikipedia and this and this $\endgroup$ Commented May 6 at 9:56
  • 5
    $\begingroup$ @Peter That's not true. See DanielWainfleet answer. $\endgroup$
    – jjagmath
    Commented May 7 at 1:21
  • 5
    $\begingroup$ @Peter The issue is your claim "Adding an element does then not change the cardinality." In the absence of (a weak form of) the axiom of choice, adding a single element to an infinite set can change its cardinality. $\endgroup$ Commented May 8 at 18:59
  • 5
    $\begingroup$ I would not be surprised if this question were a duplicate (although I don't offhand see a dupe target), but it certainly doesn't lack context. I've voted to reopen. $\endgroup$ Commented May 8 at 19:00
  • 6
    $\begingroup$ I see that this has attracted another vote to close as "Missing context." What context, exactly, is missing here? $\endgroup$ Commented May 8 at 20:16

1 Answer 1

8
$\begingroup$

Without AC, one must be cautious about "finite" and "infinite". A set $T$ is Tarski-finite iff each non-empty family of subsets of $T$ has a $\subseteqq$-minimal member. Equivalently, $T$ is Tarski-finite iff there is a bijection $f:T\to \{j\in \Bbb N_0:j<n\}$ for some $n\in \Bbb N_0$. A set $D$ is Dedekind-infinite iff there exists a bijection $g:D\to E$ for some $E\subsetneqq D$.' Since the discovery of Forcing, it has been shown that it is consistent with ZF that there exists a set $B$ which is neither Tarski-finite nor Dedekind-infinite. So if $p\in B$ and $A=B\setminus\{p\}$ and $a=|A|$ then $a+1=|B|$, so $a\ne a+1$ because that would imply a bijection $g:B\to A$, contrary to $B$ not being Dedekind-infinite. So some consequence of AC is needed.

$\endgroup$

You must log in to answer this question.

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