In mathematics, a setoid is a set (or type) equipped with an equivalence relation. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, Logic and Computer science, type theory is any of several Formal systems that can serve as alternatives to Naive set theory In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent"
Setoids are studied especially in proof theory and in type-theoretic foundations of mathematics. Proof theory is a branch of Mathematical logic that represents proofs as formal Mathematical objects facilitating their analysis by mathematical techniques In Mathematics, Logic and Computer science, type theory is any of several Formal systems that can serve as alternatives to Naive set theory Foundations of mathematics is a term sometimes used for certain fields of Mathematics, such as Mathematical logic, Axiomatic set theory, Proof theory Often in mathematics, when one defines an equivalence relation on a set, one immediately forms the quotient set (turning equivalence into equality). In Mathematics, given a set X and an Equivalence relation ~ on X, the equivalence class of an element a in X Equality is the paradigmatic example of the more general concept of Equivalence relations on a set those binary relations which are reflexive, symmetric In contrast, setoids may be used when a difference between identity and equivalence must be maintained, often with an interpretation of intensional equality (the equality on the original set) and extensional equality (the equivalence relation, or the equality on the quotient set). Not to be confused with the homophone Intention; or the related concept of Intentionality. In any of several studies that treat the use of signs for example in Linguistics, Logic, Mathematics, Semantics, and Semiotics, the
In proof theory, particularly the proof theory of constructive mathematics based on the Curry–Howard correspondence, one often identifies a mathematical proposition with its set of proofs (if any). In the Philosophy of mathematics The Curry-Howard correspondence is the direct relationship between computer programs and mathematical proofs In Logic and Philosophy, proposition refers to either (a the content or Meaning of a meaningful Declarative sentence In Mathematics, a proof is a convincing demonstration (within the accepted standards of the field that some Mathematical statement is necessarily true A given proposition may have many proofs, of course; according to the principle of proof irrelevance, normally only the truth of the proposition matters, not which proof was used. However, the Curry–Howard correspondence can turn proofs into algorithms, and differences between algorithms are often important. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation So proof theorists may prefer to identify a proposition with a setoid of proofs, considering proofs equivalent if they can be converted into one another through beta conversion or the like. In Mathematical logic and Computer science, lambda calculus, also written as λ-calculus, is a Formal system designed to investigate function
In type-theoretic foundations of mathematics, setoids may be used in a type theory that lacks quotient types to model general mathematical sets. For example, in Per Martin-Löf's Intuitionistic Type Theory, there is no type of real numbers, only a type of regular Cauchy sequences of rational numbers. Per Erik Rutger Martin-Löf (born 1942 is a Swedish Logician, Philosopher, and Mathematician. Intuitionistic type theory, or constructive type theory, or Martin-Löf type theory or just Type Theory is a Logical system and a Set theory In Mathematics, the real numbers may be described informally in several different ways In Mathematics, a Cauchy sequence, named after Augustin Cauchy, is a Sequence whose elements become arbitrarily close to each other as the sequence In Mathematics, a rational number is a number which can be expressed as a Ratio of two Integers Non-integer rational numbers (commonly called fractions To do real analysis in Martin-Löf's framework, therefore, one must work with a setoid of real numbers, the type of regular Cauchy sequences equipped with the usual notion of equivalence. Real analysis is a branch of Mathematical analysis dealing with the set of Real numbers In particular it deals with the analytic properties of real Typically (although it depends on the type theory used), the axiom of choice will hold for functions between types (intensional functions), but not for functions between setoids (extensional functions). In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory. The term "set" is variously used either as a synonym of "type" or as a synonym of "setoid"; see [1] (page 9).
References
- Martin Hofmann, A Simple Model for Quotient Types, in Typed lambda calculi and applications (Edinburgh, 1995), 216-234, Lecture Notes in Computer Science 902, Springer.
External links
In Computer science, Coq is a Proof assistant application It allows the expression of mathematical assertions mechanically checks proofs of these assertionsDapyx Software network: MP3 Explorer | Ebook Manager | Zenithic