Reducción de conjuntos


Reducción de conjuntos

Reducción de conjuntos

En teoría de la computabilidad, sean A y B dos conjuntos cualesquiera; decimos que A es reducible a B y escribimos AB, si existe una función computable total, o lo que es el equivalente, una función recursiva primitiva tal que:

A = \{ x | f(x) \in B \}

Es decir, f es una función que transforma elementos xA en elementos yB y elementos xA en elementos yB. O sea:

x\in A \Leftrightarrow f(x)\in B

Teoremas relacionados

Obtenido de "Reducci%C3%B3n de conjuntos"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Reducción de conjuntos — En teoría de la computabilidad, sean A y B dos conjuntos cualesquiera; decimos que A es reducible a B y escribimos A ≤ B, si existe una función computable total, o lo que es el equivalente, una funció …   Enciclopedia Universal

  • Conjunto recursivamente enumerable — Se denomina recursivamente enumerable (r. e.) a un conjunto, dentro de la teoría de la computabilidad, si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: Véase también Lenguaje… …   Wikipedia Español

  • Conjunto recursivamente enumerable — En teoría de la computabilidad, un conjunto se denomina recursivamente enumerable (r. e.) si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: B = x ∈ ℕ | g(x) = ↓ Ver también: ●… …   Enciclopedia Universal

  • Axiomas de Zermelo-Fraenkel — Los axiomas de Zermelo Fraenkel, formulados por Ernst Zermelo y Adolf Fraenkel, son un sistema axiomático concebido para formular la teoría de conjuntos. Normalmente se abrevian como ZF o en su forma más común, complementados por el axioma de… …   Wikipedia Español

  • Álgebra — Para los usos matemáticos de la palabra álgebra como estructura algebraica, véase álgebra no asociativa, álgebra asociativa, álgebra sobre un cuerpo. El álgebra es la rama de las matemáticas que estudia las estructuras, las relaciones y las… …   Wikipedia Español

  • Conjunto de Mandelbrot — Representación matemática del conjunto de Mandelbrot como subconjunto del plano complejo. Los puntos del conjunto se muestran en negro. Obsérvese cómo 1 pertenece al conjunto mientras que 1 no …   Wikipedia Español

  • Fosforilación oxidativa — Esquema actual del sistema mitocondrial de la fosforilación oxidativa. Los equivalentes reducidos que se generan en el metabolismo (NADH, FADH2) son oxidados por la cadena de transporte de electrones. La energía libre generada en esta reacción se …   Wikipedia Español

  • Flor — Para otros usos de este término, véase Flor (desambiguación). Partes de la flor …   Wikipedia Español

  • Historia del capitalismo — Fernand Braudel sitúa los orígenes del capitalismo en la Edad Media, en algunas pequeñas ciudades comerciantes. La historia del capitalismo ha sido objeto de grandes debates sociológicos, económicos e históricos desde el siglo XIX. El comercio… …   Wikipedia Español

  • Teoría de sistemas — La teoría general de sistemas (TGS) o teoría de sistemas o enfoque sistémico es un esfuerzo de estudio interdisciplinario que trata de encontrar las propiedades comunes a entidades llamadas sistemas. Éstos se presentan en todos los niveles de la… …   Wikipedia Español