Well-founded relation (original) (raw)
Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání.
| Property | Value |
|---|---|
| dbo:abstract | En matemàtiques, una relació binaria R està ben fonamentada en una classe X si, i només si, cada subconjunt no buit d'X té un element minimal respecte de R. Això és, per cada subconjunt no buit S de X, existeix un element m de S tal que per cada element s de S, la parella (s,m) no pertany a R: Equivalentment, assumint una elecció, una relació està ben fonamentada si, i només si, no conté cap : això és, no existeix cap seqüència infinita x0, x1, x₂, ... d'elements de X tal que xn+1 R xn per cada nombre natural n. En Teoria de l'ordre, un conjunt parcialment ordenat està ben fonamentada si l' corresponent és una relació ben fonamentada. Si l'orde és un ordre total llavors s'anomena . En Teoria de conjunts, un conjunt x s'anomena conjunt ben fonamentat si la relació de ser membre està ben formada per la de x. En aquest cas R satisfà també la . (ca) Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání. (cs) In der Mathematik heißt eine auf einer Menge definierte zweistellige Relation wohlfundiert, wenn es keine unendlichen absteigenden Ketten in dieser Relation gibt, d. h., wenn es keine unendliche Folge von Elementen in mit für alle gibt. Insbesondere enthält eine wohlfundierte Relation keine Zyklen. (de) En teoría de conjuntos, una relación bien fundada sobre una clase X es una relación binaria R sobre X tal que todo subconjunto no vacío de X tiene un elemento R-mínimo; esto es: Equivalentemente, si asumimos el axioma de elección, una relación es bien fundada si y sólo si X no contiene cadenas descendientes infinitas numerables: esto es, no hay secuencia infinita x0, x1, x2, ... de elementos de X tal que xn+1R xn para todo número natural n. * En la teoría del orden, un orden parcial es llamado bien fundado si el correspondiente es una relación bien fundada. Si el orden bien fundado es un orden total entonces es un buen orden. * Un conjunto X se dice regular si la relación de pertenencia ∈ está bien fundada en la clausura transitiva de X, ct X. Esto implica que no existen dentro de X conjuntos del tipo A={A}={{A}}=... En teoría axiomática de conjuntos, el axioma de regularidad afirma que todos los conjuntos son regulares. (es) En mathématiques, une relation bien fondée (encore appelée relation noethérienne ou relation artinienne) est une relation binaire vérifiant l'une des deux conditions suivantes, équivalentes d'après l'axiome du choix dépendant (une version faible de l'axiome du choix) : * pour toute partie non vide X de E, il existe un élément x de X n'ayant aucun R-antécédent dans X (un R-antécédent de x dans X est un élément y de X vérifiant yRx) ; * condition de chaîne descendante : il n'existe pas de suite infinie (xn) d'éléments de E telle qu'on ait xn+1Rxn pour tout n. Un ordre bien fondé (encore appelé ordre noethérien ou ordre artinien) est une relation d'ordre dont l'ordre strict associé est une relation bien fondée. Toute relation bien fondée est strictement acyclique, c'est-à-dire que sa clôture transitive est un ordre strict. Une relation R est bien fondée si sa clôture transitive l'est, ou encore si R est antiréflexive et si sa clôture réflexive transitive est un ordre bien fondé. (fr) In mathematics, a binary relation R is called well-founded (or wellfounded) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is, an element m not related by s R m (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set. Equivalently, assuming the axiom of dependent choice, a relation is well-founded when it contains no infinite descending chains, which can be proved when there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n. In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order. In set theory, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x. The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded. A relation R is converse well-founded, upwards well-founded or Noetherian on X, if the converse relation R−1 is well-founded on X. In this case R is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating. (en) 집합론에서 정초 관계(整礎關係, 영어: well-founded relation)는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 초한 귀납법(超限歸納法, 영어: transfinite induction)과 초한 재귀(超限再歸, 영어: transfinite recursion)를 사용할 수 있다. 초한 귀납법은 모든 원소가 어떤 성질을 만족시킴을 증명할 때 사용한다. 초한 귀납법에 따르면, 어떤 술어가 모든 원소에 대하여 참임을 보이려면, 주어진 원소 ‘이전’의 모든 원소들에 대하여 참임을 가정한 채로, 그 주어진 원소에 대하여 참임을 보이면 충분하다. 이는 자연수에 대한 수학적 귀납법을 일반화한다. 초한 재귀는 정초 관계가 주어진 집합을 정의역으로 하는 함수를 정의하는 방법이다. 초한 재귀에 따르면, 주어진 원소의 함숫값을 그 ‘이전’의 원소들의 함숫값들로부터 결정하는 방법(에서의 함수 )이 정해졌을 때, 모든 원소에 대한 함숫값은 유일하게 결정된다. (ko) 数学において、二項関係が整礎（せいそ、英: well-founded）であるとは、真の無限をもたないことである。 (ja) In de wiskunde heet een irreflexieve tweeplaatsige relatie op een klasse welgefundeerd, als elke niet-lege deelverzameling van een element bevat dat geen voorganger heeft, wat in dit verband betekent dat er geen element is waarvoor het paar tot de relatie behoort. Het is dus niet mogelijk dat er een hele keten van elementen is waarvan elk een voorganger heeft, die dus oneindig doorloopt. (nl) Em matemática, uma relação binária é uma relação bem-fundada numa classe X, se e somente se, todo subconjunto não vazio de X, tiver um elemento R-minimal; ou seja, para todo subconjunto não vazio S de X, existe um elemento m de S tal que para todo elemento s de S, o par (s,m) não está em R. Em outras palavras, todo subconjunto não vazio de X possui um elemento m tal que para todo s, Desta forma, evitamos situações de loop. Formalizando com a lógica de predicados, temos: Isto quando tratamos da relação de pertinência em teorias de conjuntos bem-fundados. Para uma relação R qualquer, equivalentemente podemos denotar, como o descrito no primeiro parágrafo deste artigo: , onde representa o conjunto (ou classe) das partes de X, caso X o admita (como não é o caso de classes próprias). Equivalentemente, assumindo uma função de escolha qualquer, uma relação será bem-fundada se e somente se essa relação não contiver cadeia descendente infinitamente enumerável, isto é, se não existir uma sequência x0, x1,... de elementos de X, tal que . Na teoria das estruturas ordenadas, uma ordem parcial é dita bem-fundada se a correspondente é uma relação bem-fundada. Se a ordem for uma ordem total, então ela é dita bem-ordenada. Na teoria dos conjuntos, um conjunto ß é dito um conjunto bem-fundado se a relação de pertinência for bem-fundada no fecho transitivo de ß. O axioma da regularidade, o qual é um dos axiomas na teoria dos conjuntos de Zermelo-Fraenkel, afirmando que todos os conjuntos são bem-fundados. (pt) Relacja dobrze ufundowana – relacja (zwykle częściowy porządek), dla której nie istnieje nieskończony zstępujący ciąg (każdy element tego ciągu jest w tej relacji z następującym bezpośrednio po nim). Jeśli relacja ma dowolny cykl, to nie jest dobrze ufundowana, ponieważ można wybierać po kolei elementy tego cyklu. Jeśli relacja jest skończona i nie ma cykli, to jest dobrze ufundowana. Dla nieskończonych relacji dobrze ufundowanych często można znaleźć dowolnie długą ścieżkę skończoną, na przykład dla porządku na możemy wybrać dowolnie duży element początkowy i ciąg malejący o jeden (na przykład 10-elementowy: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0). Relacja, która jest dobrze ufundowana i słabo konfluentna, jest silnie konfluentna. Relacja, która jest dobrze ufundowana i spełnia warunki porządku liniowego, jest dobrym porządkiem. (pl) В математиці, бінарне відношення R називається фундованим на класі X якщо непорожня множина S ⊆ X має мінімальний елемент по відношенню до R, тобто, такий елемент елемент m, для якого не існує s R m (для всіх s ∈ S. Формально: (uk) 在数学中，類 X 上的一个二元关系 R 被称为是良基的，当且仅当所有 X 的非空子集都有一个 R-极小元；就是说，对 X 的每一个非空子集 S，存在一个 S 中的元素 m 使得对于所有 S 中的 s，二元组 (s,m) 都不在 R 中。 等价的说，假定某种选择公理，一个二元关系称为是良基的，当且仅当它不包含可数的无穷降链，也就是说不存在 X 的元素的无穷序列 x0, x1, x2, ...使得对所有的自然数 n 有着 xn+1 R xn。 在序理论中，一个偏序关系称为是良基的，当且仅当它对应的严格偏序是良基的。如果这个序还是全序，那么此时称这个序为良序。 在集合论中，一个集合 x 称为是一个良基集合，如果集成员关系在 x 的传递闭包上是良基的。策梅洛-弗兰克尔集合论中的正则公理，就是断言所有的集合都是良基的。 (zh) |
| dbo:wikiPageID | 319712 (xsd:integer) |
| dbo:wikiPageLength | 9285 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108316869 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cartesian_product dbr:Preorder dbr:Element_(mathematics) dbr:Mostowski_collapse dbr:Binary_relation dbr:Infinite_descending_chain dbr:Thomas_Jech dbr:Transfinite_induction dbr:Course-of-values_recursion dbr:Mathematical_induction dbr:Mathematics dbr:Order_theory dbr:Ordinal_numbers dbr:Rewriting dbr:Class_(set_theory) dbr:Emmy_Noether dbr:Converse_relation dbr:Structural_induction dbr:Zermelo–Fraenkel_set_theory dbr:String_(computer_science) dbr:Total_order dbr:Well-order dbr:Divisor dbr:American_Mathematical_Society dbr:Karel_Hrbáček dbr:Marcel_Dekker dbc:Binary_relations dbr:Transfinite_recursion dbr:Directed_acyclic_graph dbr:Ascending_chain_condition dbc:Wellfoundedness dbr:Axiom_of_dependent_choice dbr:Axiom_of_regularity dbr:If_and_only_if dbr:Integer dbr:Natural_number dbr:Natural_numbers dbr:Rational_number dbr:Real_numbers dbr:Reflexive_relation dbr:Set_theory dbr:Non-empty dbr:Complete_induction dbr:Partial_order dbr:Set-like_relation dbr:Strict_order dbr:Subset dbr:Well-ordering_principle dbr:Primitive_recursive_functions dbr:Transitive_closure_(set) dbr:Lexicographic_ordering dbr:Minimal_element dbr:∈-induction dbr:Initial_segment |
| dbp:wikiPageUsesTemplate | dbt:ISBN dbt:Redirect dbt:Reflist dbt:Short_description dbt:Stack dbt:Isbn dbt:Binary_relations dbt:Mathematical_logic |
| dcterms:subject | dbc:Binary_relations dbc:Wellfoundedness |
| rdfs:comment | Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání. (cs) In der Mathematik heißt eine auf einer Menge definierte zweistellige Relation wohlfundiert, wenn es keine unendlichen absteigenden Ketten in dieser Relation gibt, d. h., wenn es keine unendliche Folge von Elementen in mit für alle gibt. Insbesondere enthält eine wohlfundierte Relation keine Zyklen. (de) 집합론에서 정초 관계(整礎關係, 영어: well-founded relation)는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 초한 귀납법(超限歸納法, 영어: transfinite induction)과 초한 재귀(超限再歸, 영어: transfinite recursion)를 사용할 수 있다. 초한 귀납법은 모든 원소가 어떤 성질을 만족시킴을 증명할 때 사용한다. 초한 귀납법에 따르면, 어떤 술어가 모든 원소에 대하여 참임을 보이려면, 주어진 원소 ‘이전’의 모든 원소들에 대하여 참임을 가정한 채로, 그 주어진 원소에 대하여 참임을 보이면 충분하다. 이는 자연수에 대한 수학적 귀납법을 일반화한다. 초한 재귀는 정초 관계가 주어진 집합을 정의역으로 하는 함수를 정의하는 방법이다. 초한 재귀에 따르면, 주어진 원소의 함숫값을 그 ‘이전’의 원소들의 함숫값들로부터 결정하는 방법(에서의 함수 )이 정해졌을 때, 모든 원소에 대한 함숫값은 유일하게 결정된다. (ko) 数学において、二項関係が整礎（せいそ、英: well-founded）であるとは、真の無限をもたないことである。 (ja) In de wiskunde heet een irreflexieve tweeplaatsige relatie op een klasse welgefundeerd, als elke niet-lege deelverzameling van een element bevat dat geen voorganger heeft, wat in dit verband betekent dat er geen element is waarvoor het paar tot de relatie behoort. Het is dus niet mogelijk dat er een hele keten van elementen is waarvan elk een voorganger heeft, die dus oneindig doorloopt. (nl) В математиці, бінарне відношення R називається фундованим на класі X якщо непорожня множина S ⊆ X має мінімальний елемент по відношенню до R, тобто, такий елемент елемент m, для якого не існує s R m (для всіх s ∈ S. Формально: (uk) 在数学中，類 X 上的一个二元关系 R 被称为是良基的，当且仅当所有 X 的非空子集都有一个 R-极小元；就是说，对 X 的每一个非空子集 S，存在一个 S 中的元素 m 使得对于所有 S 中的 s，二元组 (s,m) 都不在 R 中。 等价的说，假定某种选择公理，一个二元关系称为是良基的，当且仅当它不包含可数的无穷降链，也就是说不存在 X 的元素的无穷序列 x0, x1, x2, ...使得对所有的自然数 n 有着 xn+1 R xn。 在序理论中，一个偏序关系称为是良基的，当且仅当它对应的严格偏序是良基的。如果这个序还是全序，那么此时称这个序为良序。 在集合论中，一个集合 x 称为是一个良基集合，如果集成员关系在 x 的传递闭包上是良基的。策梅洛-弗兰克尔集合论中的正则公理，就是断言所有的集合都是良基的。 (zh) En matemàtiques, una relació binaria R està ben fonamentada en una classe X si, i només si, cada subconjunt no buit d'X té un element minimal respecte de R. Això és, per cada subconjunt no buit S de X, existeix un element m de S tal que per cada element s de S, la parella (s,m) no pertany a R: Equivalentment, assumint una elecció, una relació està ben fonamentada si, i només si, no conté cap : això és, no existeix cap seqüència infinita x0, x1, x₂, ... d'elements de X tal que xn+1 R xn per cada nombre natural n. (ca) En teoría de conjuntos, una relación bien fundada sobre una clase X es una relación binaria R sobre X tal que todo subconjunto no vacío de X tiene un elemento R-mínimo; esto es: Equivalentemente, si asumimos el axioma de elección, una relación es bien fundada si y sólo si X no contiene cadenas descendientes infinitas numerables: esto es, no hay secuencia infinita x0, x1, x2, ... de elementos de X tal que xn+1R xn para todo número natural n. (es) En mathématiques, une relation bien fondée (encore appelée relation noethérienne ou relation artinienne) est une relation binaire vérifiant l'une des deux conditions suivantes, équivalentes d'après l'axiome du choix dépendant (une version faible de l'axiome du choix) : * pour toute partie non vide X de E, il existe un élément x de X n'ayant aucun R-antécédent dans X (un R-antécédent de x dans X est un élément y de X vérifiant yRx) ; * condition de chaîne descendante : il n'existe pas de suite infinie (xn) d'éléments de E telle qu'on ait xn+1Rxn pour tout n. (fr) In mathematics, a binary relation R is called well-founded (or wellfounded) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is, an element m not related by s R m (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set. (en) Relacja dobrze ufundowana – relacja (zwykle częściowy porządek), dla której nie istnieje nieskończony zstępujący ciąg (każdy element tego ciągu jest w tej relacji z następującym bezpośrednio po nim). Jeśli relacja ma dowolny cykl, to nie jest dobrze ufundowana, ponieważ można wybierać po kolei elementy tego cyklu. Jeśli relacja jest skończona i nie ma cykli, to jest dobrze ufundowana. Relacja, która jest dobrze ufundowana i słabo konfluentna, jest silnie konfluentna. Relacja, która jest dobrze ufundowana i spełnia warunki porządku liniowego, jest dobrym porządkiem. (pl) Em matemática, uma relação binária é uma relação bem-fundada numa classe X, se e somente se, todo subconjunto não vazio de X, tiver um elemento R-minimal; ou seja, para todo subconjunto não vazio S de X, existe um elemento m de S tal que para todo elemento s de S, o par (s,m) não está em R. Em outras palavras, todo subconjunto não vazio de X possui um elemento m tal que para todo s, Desta forma, evitamos situações de loop. Formalizando com a lógica de predicados, temos: Isto quando tratamos da relação de pertinência em teorias de conjuntos bem-fundados. (pt) |
| rdfs:label | Relació ben fonamentada (ca) Fundovaná relace (cs) Wohlfundierte Relation (de) Relación bien fundada (es) Relation bien fondée (fr) Relazione ben fondata (it) 整礎関係 (ja) 정초 관계 (ko) Welgefundeerde relatie (nl) Relacja dobrze ufundowana (pl) Relação bem-fundada (pt) Well-founded relation (en) 良基关系 (zh) Фундоване відношення (uk) |
| owl:sameAs | freebase:Well-founded relation wikidata:Well-founded relation dbpedia-ca:Well-founded relation dbpedia-cs:Well-founded relation dbpedia-de:Well-founded relation dbpedia-es:Well-founded relation dbpedia-fr:Well-founded relation dbpedia-he:Well-founded relation dbpedia-hu:Well-founded relation dbpedia-it:Well-founded relation dbpedia-ja:Well-founded relation dbpedia-ko:Well-founded relation dbpedia-nl:Well-founded relation dbpedia-pl:Well-founded relation dbpedia-pt:Well-founded relation dbpedia-sk:Well-founded relation dbpedia-uk:Well-founded relation dbpedia-vi:Well-founded relation dbpedia-zh:Well-founded relation https://global.dbpedia.org/id/379fp |
| prov:wasDerivedFrom | wikipedia-en:Well-founded_relation?oldid=1108316869&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Well-founded_relation |
| is dbo:wikiPageRedirects of | dbr:Noetherian_induction dbr:Well-founded_induction dbr:Well-founded dbr:Well-founded_recursion dbr:Well-foundedness dbr:Wellfounded dbr:Wellfounded_induction dbr:Wellfounded_recursion dbr:Wellfoundedness dbr:Noetherian_recursion dbr:Hereditarily_well-founded_set dbr:Noetherian_relation dbr:Wellfounded_relation dbr:Well-founded_set dbr:Well-founded_order dbr:Well-founded_relations dbr:Well_founded |
| is dbo:wikiPageWikiLink of | dbr:Prewellordering dbr:Rose_tree dbr:Mostowski_collapse_lemma dbr:Lévy_hierarchy dbr:Noetherian_induction dbr:Homogeneous_relation dbr:Relation_(mathematics) dbr:Dershowitz–Manna_ordering dbr:Infinite_regress dbr:List_of_order_theory_topics dbr:Transfinite_induction dbr:Predicate_transformer_semantics dbr:Well-founded_induction dbr:Constructible_universe dbr:Order_theory dbr:Ordinal_collapsing_function dbr:Epsilon-induction dbr:Epsilon_number dbr:Ordinal_analysis dbr:Admissible_rule dbr:Well-founded dbr:Well-founded_recursion dbr:Well-foundedness dbr:Well-order dbr:Well-quasi-ordering dbr:Wellfounded dbr:Wellfounded_induction dbr:Wellfounded_recursion dbr:Wellfoundedness dbr:Noetherian_recursion dbr:Hilbert's_problems dbr:Hereditarily_well-founded_set dbr:Hereditary_set dbr:Hoare_logic dbr:Termination_analysis dbr:Provability_logic dbr:Axiom_of_regularity dbr:Inductive_type dbr:Newman's_lemma dbr:Kleene's_O dbr:Kleene–Brouwer_order dbr:Loop_variant dbr:WFO dbr:Implementation_of_mathematics_in_set_theory dbr:Noetherian_relation dbr:Safety_and_liveness_properties dbr:Outline_of_logic dbr:Wellfounded_relation dbr:Well-founded_set dbr:Well-founded_order dbr:Well-founded_relations dbr:Well_founded |
| is foaf:primaryTopic of | wikipedia-en:Well-founded_relation |