Does Level IV Multiverse/Ultimate Multiverse contains 'impossible worlds'? Does Level IV Multiverse/Ultimate Multiverse contains 'impossible worlds'? Does it contain universes with sets, structures, or systems that exist beyond spacetime, duality, or existence and nonexistence?
Does it contains universes with different laws of logic or metaphysics than ours?
Does it contain universes with wholly alien or incomprehensible concepts, or contains impossible worlds?
 A: Some caveats below:
1) Equating a formal system (theory) to a universe is imprecise, because most formal systems have an infinite number of different structures that satisfy their axioms and theorems. This is related to the fact that most formal theories are incomplete (Godel), and they can be completed in an infinite number of ways. But in order to complete a theory you need to assume an infinite number of axioms, and this is not something that can be described in a finite way. So it would be more precise to equate a multiverse to a complete theory, and thus to a single mathematical structure. 
2) But what is a structure?  The problem is that any theory (complete or not) can also be described in infinitely many different ways. For instance, you can chose a set theoretical description, and thus everything are sets. Or you can use an equivalent description based on category theory, and then all you have are collections of objects and arrows. 
Thus, do you have a different multiverse for sets, categories, etc, even if they represent the same theory? You should perhaps fix this ambiguity by equating a multiverse  to a single abstract structure, a structure that is not made of sets, points, numbers, triangles or anything specific but that however can be represented by any of them.
To conclude, what is a valid multiverse? I do not know.
UPDATE:
I just read mag tegmark paper for more details. He restricts his multiverse to  Computable structures (whose relations are defined
by halting computations), and he states that a structure, or a distinct multiverse, is actually the class of equivalence of equivalent computable structures. Thus only finitist universes qualify.
That means that he avoids problem (1) by restricting the kind of formal systems that have multiverses. For instance, using his definition any theory that contains Peano arithmetics does not qualify as a multiverse because it is incomplete, or non computable.  Triangles, for instance  (if they live in the real plane), do not exist, only pixelated ones do.
He also tries to avoid problem (2) by stating that all formal systems that are computationally equivalent correspond to the same multiverse.
This is not as intuitive as it seems. Different formal systems describing the same structure differ on what is considered a "basic element" and what is considered a "relationship" between these elements. For instance, a given multiverse can be described by different turing machines, all computing the same equivalent class of structures, but each machine differing on what is the number of allowed alphabet letters, internal states, and transition rules. 
To conclude, each multiverse does not correspond to what we intuitively think of a mathematical structure (for instance, the real plane): A single multiverse is a more abstract step from it that includes all structures equivalent to it by means of a computation (that is, any transformation, or "re-packaging", of equivalent basic elements and relationships that can be made in a finite number of steps)
In this sense, for instance, there is no such thing as a multiverse made of "triangles", or of any other specific mathematical structures that you are used to think. In the same way, any physical theory that you can propose correspond to an individual multiverse, but that same individual multiverse can come from an infinite number of different theories. The relationship between theory and multiverse is not one to one.
A: The Level IV Multiverse is meant to contain all universes which can be described by different mathematical structures, according to Wikipedia. So it certainly contains universes that might have "totally alien or incomprehensible concepts", or universes with "different laws of logic or metaphysics" as long as those laws of logic constitute a system of mathematical structures. This also means that spacetime, existence, duality, and what have you may not be a thing in these alternate universes, as long as, of course, the laws that do govern the universe can be described by various mathematical structures. However, the definition of impossible worlds you seem to be using (you linked to this article) seems to imply that the impossible world cannot be described by a consistent set of logical, mathematical laws, which contradicts our original definition of the Level IV Multiverse. So (if I understand your definition correctly) I would say impossible worlds aren't included in the Level IV Multiverse.
Hope this helps!
A: I am not sure how to answer this because I think the type IV many worlds is not well formulated. The observable universe has a range of mathematical descriptions, from symplectic geometry for classical mechanics, Riemannian geometry for general relativity, Hilbert space for quantum mechanics, stochastic modelling for various processes and so forth. We might then ask about something like economics, a subject that so far does not have a single mathematical description. We might then ask whether there are multiple worlds with different maths for economics, and we are groping around to find the one optimal for "our world." I am not so sure about that kind of proposition. 
In the Mathematical Universe Hypothesis of Tegmark there may exist alternate worlds that obey mathematics we may not even yet know about and which do not apply in the observable world. The problem with this is that it is hard to know how to make mathematics, a subject that involves theorem-proofs, connect this directly with physics that is ultimately an empirical science. Also mathematics is open and almost (or absolutely) infinitely variable, while physics that is really constrained by observation is not so "liberal." 
If there are alternate universes then it is not likely they are self-contradicting however. That does not seem to make sense. They might though in many cases be Godelian or highly self-referential and not easily understood by any means. 
