It is generally known that infinite symmetric groups have few nontrivial normal subgroups (typically only the subgroups of bounded support) and none of small index. (We will explain later exactly what we mean by small). However the standard analysis relies heavily on the axiom of choice. By dint of a lot of combinatorics we have been able to dispense—largely—with the axiom of choice. Largely, but not entirely: our result is that if X is an infinite set with ∣X∣ = ∣X × X∣ then Symm(X) has no nontrivial normal subgroups of small index. Some condition like this is needed because of the work of Sam Tarzi who showed [4] that, for any finite group G, there is a model of ZF without AC in which there is a set X with Symm(X)/FSymm(X) isomorphic to G.

The proof proceeds in two stages. We consider a particularly useful class of permutations, which we call the class of flexible permutations. A permutation of X is flexible if it fixes at least ∣X∣-many points. First we show that every normal subgroup of Symm(X) (of small index) must contain every flexible permutation. This will be theorem 4. Then we show (theorem 7) that the flexible permutations generate Symm(X).

We introduce the notion of skinniness for subsets of and its variants, namely skinnier and skinniest. We show that under some cardinal arithmetical assumptions, precipitousness or 2λ-saturation of NSκλ ∣ X, where NSκλ denotes the non-stationary ideal over , implies the existence of a skinny stationary subset of X. We also show that if λ is a singular cardinal, then there is no skinnier stationary subset of . Furthermore, if λ is a strong limit singular cardinal, there is no skinny stationary subset of . Combining these results, we show that if λ is a strong limit singular cardinal, then NSκλ ∣ X can satisfy neither precipitousness nor 2λ-saturation for every stationary X ⊆ . We also indicate that , where , is equivalent to the existence of a skinnier (or skinniest) stationary subset of under some cardinal arithmetical hypotheses.

In this paper we prove:

Theorem 1. Any finite model of the axiom of power-set also satisfies the axioms of extensionality, sum-set and choice.

Clearly, it will follow from (2) below that in a finite model the axiom of power-set is satisfied if and only if every set is a power-set. Thus, Theorem 1 follows immediately from Theorem 2 below, where by a theory of sets we mean a first-order theory without identity and with only one binary predicate symbol ∈.

Theorem 2. If in a theory of sets every set is a power-set and if the axiom of power-set is valid, then the axioms of extensionality, sum-set and choice are valid.

The proof of Theorem 2 will follow from the lemmas which we establish below.

We mean by x = y that x and y have the same elements. We denote a power-set of x by P(x) when it exists; similarly, we denote a sum-set of x by Ux.

Clearly, in every theory of sets we have:

(1) (x ⊂ y) ↔ (P(x) ⊂ P(y)),

(2) (x = y) ↔ (P(x) = P(y)),

(3) (x = y) → ((x ∈ P(z)) → (y ∈ P(z))),

(4) ⋃P(x) = x.

In view of (2), (3) and the definition of equality, we have:

Lemma 1. If in a theory of sets every set is a power-set, then equal sets are elements of the same sets.

We have also, in view of (4):

Lemma 2. If in a theory of sets every set is a power-set, then every set has a sum-set.

Professor R. L. Goodstein's neat proposal for formalising and proving the Policeman — the logical truth mentioned in my paper — illustrates the main thesis of that paper, viz., that in formalising the logic of indirect discourse one needs to avoid assigning what was said, and the report that it was said, to different levels of a semantical hierarchy. But there are two main difficulties in his proposal:

1. It is not quite clear whether the axioms and rules of Prof. Goodstein's system are to be such that substitutivity of the biconditional is maintained for all wff. If so, the system takes no account of the referentially opaque quality of indirect discourse. For example, the analogue for “If Sir Walter Scott always says the same as the author of Waverley, then George III says that anything Sir Walter Scott says is true if and only if George III says that anything the author of Waverley says is true” would be provable, though this statement is not logically true. If “A(x){Bx→x)” is well-formed (as it must be for Professor Goodstein's proof), the corresponding theorem is

2. In interpreting the letters “A”, “B”, etc. as operators, so that sentences are the substitution-instances both for variables like “x” and for schematic functions of those variables like “Ax”, Professor Goodstein's system does not provide for formalising logical truths in which ordinary predication also plays a part: e.g., “If the policeman says that all women are dangerous drivers and anything the policeman says is true, then no non-dangerous drivers are women”.

To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >stA) if for every computable function f, for all but finitely many x, mB(x) > f(mA(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <st ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it. that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g, for almost all x, mB(x) > f(mA(g(x))).

It is known that the usual definition of a dense series without extreme elements is complete with respect to first-order functions, in the sense that any first-order function on the base of a set of postulates defining such a series either is implied by the postulates or is inconsistent with them. It is here understood, in accordance with the usual convention, that when we speak of a function on the base , the function shall be such as to place restrictions only upon elements belonging to the class determined by f; or, more exactly, every variable with a universal prefix shall occur under the hypothesis that its values satisfy f, while every variable with an existential prefix shall have this condition categorically imposed upon it.

Consider a set of postulates defining a dense series without extreme elements, and add to this set the condition of Dedekind section, to be formulated as follows. Let the conjunction of the three functions,

be written H(ϕ), where the free variables f and g, being parameters throughout, are suppressed. This is the hypothesis of Dedekind's condition, and the conclusion is

which may be written C(ϕ).

We give three counterexamples to the folklore claim that in an arbitrary theory, if a complete type p over a set B does not divide over $C\subseteq B$, then no extension of p to a complete type over $\operatorname {acl}(B)$ divides over C. Two of our examples are also the first known theories where all sets are extension bases for nonforking, but forking and dividing differ for complete types (answering a question of Adler). One example is an $\mathrm {NSOP}_1$ theory with a complete type that forks, but does not divide, over a model (answering a question of d’Elbée). Moreover, dividing independence fails to imply M-independence in this example (which refutes another folklore claim). In addition to these counterexamples, we summarize various related properties of dividing that are still true. We also address consequences for previous literature, including an earlier unpublished result about forking and dividing in free amalgamation theories, and some claims about dividing in the theory of generic $K_{m,n}$-free incidence structures.

C-systems were defined by Cartmell as models of generalized algebraic theories. B-systems were defined by Voevodsky in his quest to formulate and prove an initiality conjecture for type theories. They play a crucial role in Voevodsky’s construction of a syntactic C-system from a term monad. In this work, we construct an equivalence between the category of C-systems and the category of B-systems, thus proving a conjecture by Voevodsky.

We explore the possibilities for elementary embeddings $j : M \to N$ , where M and N are models of ZFC with the same ordinals, $M \subseteq N$ , and N has access to large pieces of j. We construct commuting systems of such maps between countable transitive models that are isomorphic to various canonical linear and partial orders, including the real line ${\mathbb R}$ .

Assume $G\prec H$ are groups and ${\cal A}\subseteq {\cal P}(G),\ {\cal B}\subseteq {\cal P}(H)$ are algebras of sets closed under left group translation. Under some additional assumptions we find algebraic connections between the Ellis [semi]groups of the G-flow $S({\cal A})$ and the H-flow $S({\cal B})$. We apply these results in the model theoretic context. Namely, assume G is a group definable in a model M and $M\prec ^* N$. Using weak heirs and weak coheirs we point out some algebraic connections between the Ellis semigroups $S_{ext,G}(M)$ and $S_{ext,G}(N)$. Assuming every minimal left ideal in $S_{ext,G}(N)$ is a group we prove that the Ellis groups of $S_{ext,G}(M)$ are isomorphic to closed subgroups of the Ellis groups of $S_{ext,G}(N)$.