I’m trying to create a permutation model $N$ in which every infinite set is weakly Dedekind-infinite (i.e. for every infinite set $A\in N$ there is a surjective map $f:A\rightarrow\omega$ in $N$), but the model contains an infinite $B\in N$ which is not Dedekind-infinite (i.e. there is no injective function $f:\omega\rightarrow B$ in $N$). I’ve been struggling, so if anyone can help me out that would be greatly appreciated.
Set Theory – Permutation Model with Weakly Dedekind-Infinite but Not Dedekind-Infinite Sets
elementary-set-theorymodel-theoryset-theory
Related Solutions
As Asaf pointed out, it is not true that $\omega$ is in every model of ZF. It is not even true that every model $(M,E)$ of ZF has a set $X$ such that $(X,E \restriction X \times X)$ is isomorphic to $(\omega, \mathord{\in} \restriction \omega \times \omega)$.
Instead I will answer the question I think you may have meant to ask, namely "what sets are in every transitive model of ZF?"
The sets that are in every transitive model of ZF are the ones that are in $L_\alpha$, the $\alpha^\text{th}$ level of Goedel's constructible universe $L$, where $\alpha$ is least such that $L_\alpha$ satisfies ZF. This is because if $M$ is a transitive model of ZF then $L^M$ is a level of $L$.
By the way, it makes no formal sense to say "an axiom implies $X$" or even "an axiom implies the existence of $X$" where $X$ is a set. What does make sense is to say "an axiom implies the existence of a set $X$ with property $P$." This makes sense because "there exists a set $X$ with property $P$" is a statement. Axioms imply statements, not sets. Of course it should not be against the law to say imprecise things but I think in this case it may be causing you confusion.
EDIT:
ZF proves that the class of all finite ordinals, denoted $\omega$, exists as a set. If $(M, \in)$ is a transitive model of ZF, then $\omega^M$, which is the element of $M$ that the model $(M,\in)$ thinks is the class of all finite ordinals, is equal to $\omega$ itself. Moreover the finite ordinals of $M$ are exactly the finite ordinals.
The class of all ordinals of $M$, denoted $\text{Ord}^M$, is an initial segment of $\text{Ord}$, the class of all ordinals. If $M$ is a set rather than a proper class, then some ordinals will be missing from $\text{Ord}^M$. In this case $\text{Ord}^M$ is itself an ordinal.
By the Loewenhein–Skolem theorem, $M$ may be countable, in which case $M$ does not contain any uncountable ordinals and $\text{Ord}^M$ is a countable ordinal. However, by Cantor's theorem applied in $(M,\in)$, there are many ordinals in $M$ that are uncountable in $M$ even though they are countable in $V$. This (roughly) is known as Skolem's paradox.
Real numbers can be coded as subsets of $\omega$ in an absolute way, so because $\omega^M = \omega$, $\mathbb{R}^M$ is a subset of $\mathbb{R}$. However, equality can fail: for example, if $M$ is countable then $\mathbb{R}^M$ is countable and therefore cannot be equal to $\mathbb{R}$.
The two definitions are certainly not equivalent.
Suppose that $A$ is any infinite Dedekind-finite set. Let $S$ be the set of finite injective sequences from $A$, namely, all the injective functions from a natural number into $A$.
Claim. $S$ is Dedekind-finite.
Proof. Suppose not, then we have a countably infinite subset of sequences, $f_n$ for $n<\omega$, and without loss of generality $f_n\neq\varnothing$ for all $n<\omega$ as well, otherwise just omit that one empty function. Define the following function by recursion $F(0)=f_0(0)$; $F(n+1)=f_n(k)$ where $n$ is the least such that for some $k\in\operatorname{dom}(f_n)$, $F(i)\neq f_n(k)$ for all $i\leq n$. This is well-defined since the first $n$ functions enumerated only a finite union of finite sets, and there are only finitely many injections from a finite ordinal into a finite set, so there will be some $n$ and $k$.
In other words, go through the functions in order, and along their domains, in order, and when you find a new element you've not encountered before, add it to your list.
Easily, $F$ is injective and with domain $\omega$. So $A$ must be Dedekind-infinite, which is a contradiction. So, indeed, $S$ is Dedekind-finite. $\square$
Claim. There is a surjection from $S$ onto itself which is not a bijection.
Proof. Let $f\in S$, if $f=\varnothing$, then $f\mapsto f$; otherwise, the domain of $f$ is some $n+1$, simply define $f\mapsto f\restriction n$. In other words, remove the last point from each sequence, if such point exists.
Easily, this function is a surjection, and it is certainly not a bijection since any $1$-tuple is mapped to the empty function, as well as the empty function itself.
So, what we have shown is that if there is any kind of Dedekind-finite set, then there is one which is $*$-Dedekind-infinite.
To your second question, since you've proved the equivalences of all the others, let me use that.
Assuming (2), or equivalently (4), we can take either $B$ to be a proper subset of $A$ of the same cardinality, or $A=\cup\{x\}$ for some $x\notin A$. So we get the case that $B\subsetneq A$ or $A\subsetneq B$, respectively. In both cases, exactly one of $A\setminus B$ and $B\setminus A$ is empty.
So (1)–(4) all imply (5).
In the other direction, assume that there is no bijection between $A\setminus B$ and $B\setminus A$ and let $f\colon A\to B$ be a bijection.
Then we know that either there is some $a\in A\setminus B$ such that $f(a)\in A\cap B$ or there is some $b\in B\setminus A$ such that $f^{-1}(b)\in A$. Since otherwise, $f\restriction A\setminus B\to B\setminus A$ would have been a bijection.
Let's consider all the images and preimages of points in $A$ that are in $A$; and let's do the same for those in $B$ (by $f^{-1}$). So given a point $a\in A$, if $f(a)\in A$, or $f^{-1}(a)\in A$, we will chart that course. Once we've hit $B\setminus A$ or $A\setminus B$, we stop. Now let's consider our cases.
There is some $a\in A$ with an infinite orbit. In this case, we have (3) holds, so $A$ is Dedekind-infinite.
There are no infinite orbits. But if $a\in A\setminus B$ or $b\in B\setminus A$, then the orbits of $a$ and $b$ must not only be finite, but linear and satisfy these two properties:
If $f^n(a)$ is the last point in the orbit, then $f^{n+1}(a)\in B\setminus A$. Otherwise, we can continue and apply $f$ for longer.
If $a\notin A\setminus B$, then it is the only point in that orbit satisfying that property. Because $f\colon A\to B$, it is impossible for a point in $A\setminus B$ to be in the image of $f$.
The two properties have versions for $b\in B\setminus A$, of course. However, what it means is that we can identify for each $a\in A\setminus B$, some $b\in B\setminus A$ which is uniquely determined by some finitely many applications of $f$. In other words, $f$ determines an injection from $A\setminus B$ into $B\setminus A$, and likewise $f^{-1}$ determines an injection in the other direction. By Cantor–Bernstein, this means that $A\setminus B$ and $B\setminus A$ have the same cardinality.
Therefore, either $A$ is Dedekind-infinite, or $A\setminus B$ and $B\setminus A$ have the same cardinality. Since we assumed the latter failed, it must be that the former holds. $\square$
Best Answer
The second Fraenkel model (in the terminology of Jech's AOC monagraph, see section 4.4) is a permutation model that has these properties.
The model is constructed as follows: We start with countably-many atoms grouped like $A = \bigcup_n \{a_n,b_n\}$, consider the group of permutations $\pi$ such that for all $n,$ either $\pi a_n= a_n$ and $\pi b_n = b_n,$ or $\pi a_n= b_n$ and $\pi b_n = a_n$, and then take the permutation model $\mathcal V$ of this group with finite supports.
As usual for finite supports, $A$ is infinite and Dedekind-finite in $\mathcal V$: For any $f:\omega \to A$ with infinite range and any finite $E\subseteq A,$ there is an $n$ such that $a_n,b_n\notin E$ and either $a_n$ or $b_n$ in the range of $f.$ Then the $\pi$ that just swaps $a_n$ and $b_n$ fixes $E$ and has $\pi f \ne f,$ and thus $f\notin \mathcal V.$
But unlike the other two permutation models Jech studies in chapter $4,$ note that $A$ is not weakly Dedekind-finite: The surjection $A\to \omega$ given by $a_n\mapsto n$ and $b_n\mapsto n$ is clearly symmetric with support $\emptyset$.
To show that every infinite set is weakly Dedekind-infinite in $\mathcal V,$ we can use the fact that $\mathcal V$ satisfies the axiom of multiple choice (i.e. for any collection $X$ of nonempty sets, there is a function $f$ on $X$ such that for all $x\in X,$ $f(x)$ is a finite subset of $x$), which is proven as part of Jech's theorem 9.2. The idea of the proof is that for any nonempty $X\in \mathcal V$ and $x\in X,$ the set $G(X,x) = \{\pi x: \pi X = X\}$ is finite, since $\pi x$ only determined by what $\pi$ does on the support of $x$, and is clearly unchanged by any $\pi$ with $\pi X= X.$ By choosing a canonical $X$ and $x$ in each orbit of the full group and defining $F(\rho X) = \rho G(X,x)$, we can see $F$ is a symmetric multiple choice function on $\mathcal V.$
So with that result, it just remains to show multiple choice implies every infinite set is weakly Dedekind-infinite. Let $X$ be infinite and for $n\in \omega,$ let $X_n = \{Y\subseteq X: |Y|=n\}.$ Let $Y_n$ be a multiple choice sequence from $X_n$ and let $Y'_n = \cup Y_n,$ so each $Y_n'$ is a finite subset of $X$ with size $\ge n.$ Then by finding the next $Y_n$ with new elements (which always will exist since the size keeps growing) and taking the new elements, we can get a sequence $Z_n$ of disjoint nonempty subsets of $X.$ Then for $x\in X,$ define $g(x)$ be the unique $n$ such that $x\in Z_n$ if $x\in \bigcup_n Z_n,$ and otherwise let $g(x) =0$, and $g$ is a surjection $X\to \omega.$
It should be noted that this only establishes independence of the two propositions over ZFA, and the argument seems unpromising to transfer to ZF since multiple choice is equivalent to choice over ZF. (Also, according to Howard and Rubin, which may be outdated, it's unknown if every infinite set is weakly Dedekind infinite in the second Cohen model.) However, as noted in the comments, the basic Cohen model witnesses independence over ZF, and exercise 5.20 in Jech sketches the argument.