The Experts below are selected from a list of 261 Experts worldwide ranked by ideXlab platform

T. B. M. Mcmaster - One of the best experts on this subject based on the ideXlab platform.

  • Realizing Quasiordered Sets by Subspaces of ‘Continuum-Like’ Spaces
    Order, 1998
    Co-Authors: A. E. Mccluskey, T. B. M. Mcmaster
    Abstract:

    Given an ordered set E and a topological space X, we say that E can be realized within X if there is an injection j from E into the class of (homeomorphism classes of) subspaces of X such that, for x, y in E, x ≤ y if and only if j(x) is homeomorphically embeddable into j(y). It is known, for instance, that Transfinite Induction demonstrates that every partially-ordered set of cardinality c (and some larger ones) can be realized within the real line. We explore aspects of the realizability problem, indicating, in particular, how to weaken the hypothesis on E from partial- to quasi-order, and seeking to isolate the characteristics of the real line that are relevant here.

  • On chains and posets within the power set of a continuum
    International Journal of Mathematics and Mathematical Sciences, 1995
    Co-Authors: P. T. Matthews, T. B. M. Mcmaster
    Abstract:

    Transfinite Induction is employed to construct a copy of an arbitrary partially-ordered set of cardinality at most c within the power set (quasi-ordered by sub-chain embeddability) of the real line.

Carsten Schürmann - One of the best experts on this subject based on the ideXlab platform.

  • Lexicographic Path Induction
    2010
    Co-Authors: Jeffrey Sarnat, Carsten Schürmann
    Abstract:

    Abstract. Programming languages theory is full of problems that reduce to proving the consistency of a logic, such as the normalization of typed lambda-calculi, the decidability of equality in type theory, equivalence testing of traces in security, etc. Although the principle of Transfinite Induction is routinely employed by logicians in proving such theorems, it is rarely used by programming languages researchers who often prefer alternatives such as proofs by logical relations and model theoretic constructions. In this paper we harness the well-foundedness of the lexicographic path ordering to derive an Induction principle that combines the comfort of structural Induction with the expressive strength of Transfinite Induction. Using lexicographic path Induction, we give a consistency proof of Martin-Löf’s intuitionistic theory of inductive definitions. The consistency of Heyting arithmetic follows directly, and weak normalization for Gödel’s T follows indirectly; both have been formalized in a prototypical extension of Twelf.

  • TLCA - Lexicographic Path Induction
    Lecture Notes in Computer Science, 2009
    Co-Authors: Jeffrey Sarnat, Carsten Schürmann
    Abstract:

    Programming languages theory is full of problems that reduce to proving the consistency of a logic, such as the normalization of typed lambda-calculi, the decidability of equality in type theory, equivalence testing of traces in security, etc. Although the principle of Transfinite Induction is routinely employed by logicians in proving such theorems, it is rarely used by programming languages researchers, who often prefer alternatives such as proofs by logical relations and model theoretic constructions. In this paper we harness the well-foundedness of the lexicographic path ordering to derive an Induction principle that combines the comfort of structural Induction with the expressive strength of Transfinite Induction. Using lexicographic path Induction, we give a consistency proof of Martin-Lof's intuitionistic theory of inductive definitions. The consistency of Heyting arithmetic follows directly, and weak normalization for Godel's T follows indirectly; both have been formalized in a prototypical extension of Twelf.

Ulrich Berger - One of the best experts on this subject based on the ideXlab platform.

Yves Nievergelt - One of the best experts on this subject based on the ideXlab platform.

  • Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications
    2015
    Co-Authors: Yves Nievergelt
    Abstract:

    Preface.- 1. Propositional Logic: Proofs from Axioms and Inference Rules.- 2. First Order Logic: Proofs with Quantifiers.- 3. Set Theory: Proofs by Detachment, Contraposition, and Contradiction.- 4. Mathematical Induction: Definitions and Proofs by Induction.- 5. Well-Formed Sets: Proofs by Transfinite Induction with Already Well-Ordered Sets.- 6. The Axiom of Choice: Proofs by Transfinite Induction.- 7. Applications: Nobel-Prize Winning Applications of Sets, Functions, and Relations.- 8. Solutions to Some Odd-Numbered Exercises.- References.- Index.

  • The Axiom of Choice: Proofs by Transfinite Induction
    Logic Mathematics and Computer Science, 2015
    Co-Authors: Yves Nievergelt
    Abstract:

    This chapter presents several statements, which are called “principles” because they are well-formed formulae but not propositions, in the sense that neither of them nor their negations are theorems, in the Zermelo-Fraenkel set theory. The first sections show how Zorn’s Maximal-Element Principle implies Zermelo’s Well-Ordering Principle, which in turn implies the Choice Principle. Thus any extension of the Zermelo-Fraenkel set theory that includes Zorn’s Maximal-Element Principle as an axiom also includes the other two principles as theorems. From the Choice Principle, subsequent sections demonstrate the converse implications, known as Zorn’s Lemma and Zermelo’s Theorem, so that all three principles are logically equivalent within the Zermelo-Fraenkel set theory. Hence all three principles are theorems in the Zermelo-Fraenkel-Choice set theory, which includes the Choice Principle as the Axiom of Choice. The material also introduces yet other principles that are logically equivalent to the Axiom of Choice, for example, the principle of the distributivity of intersections over unions of families of sets. Any theory that requires any such equivalent principle thus also requires the Axiom of Choice. Other consequences of the Axiom of Choice include the existence of extrema for continuous functions on closed and bounded sets in Euclidean spaces.

  • well formed sets proofs by Transfinite Induction with already well ordered sets
    2015
    Co-Authors: Yves Nievergelt
    Abstract:

    This chapter focuses on “well-formed” sets, which are defined by means restricted to the axioms of Zermelo-Fraenkel set theory from chapters 1, 2, 3, and 4. The main result states that no two well-formed sets are members of each other, and consequently that every well-formed set is not an element of itself.

Zoltán Vidnyánszky - One of the best experts on this subject based on the ideXlab platform.

  • Transfinite Inductions producing coanalytic sets
    Fundamenta Mathematicae, 2014
    Co-Authors: Zoltán Vidnyánszky
    Abstract:

    A. Miller proved the consistent existence of a coanalytic two-point set, Hamel basis and MAD family. In these cases the classical Transfinite Induction can be modified to produce a coanalytic set. We generalize his result formulating a condition which can be easily applied in such situations. We reprove the classical results and as a new application we show that in $V=L$ there exists an uncountable coanalytic subset of the plane that intersects every $C^1$ curve in a countable set.