Notación Set-builder, Los juegos de construcción, Los predicados equivalentes Builder significa conjuntos equivalentes, La paradoja de Russell, Variaciones

En la teoría de conjuntos y sus aplicaciones a la lógica, las matemáticas y la informática, la notación set-builder es una notación matemática para describir un conjunto declarando las propiedades que sus miembros deben satisfacer. La formación de conjuntos de este modo también se conoce como conjunto de comprensión, conjunto abstracción o como la definición de la intensión de un conjunto. Aunque algunos simplemente se refieren a ella como la notación de conjuntos, la etiqueta puede ser mejor reservado para la clase más amplia de los medios de que denota sets.

Los juegos de construcción

Sea F una fórmula en la que x aparece libre. Establecer la notación constructor tiene la forma {x: F}, que denota el conjunto de todos los individuos en el universo del discurso que satisface la fórmula F, es decir, el conjunto cuyos miembros son cada individuo y tal que F es cierta: formalmente, la ampliación de el predicado. A veces, el universo de discurso está establecido en la notación, la escritura {x? U: F} establece que el universo de discurso es de U para los propósitos del conjunto que se está construyendo, aunque esto se hace a costa de hacer que el operador de miembro determinada ambigua en la notación formal fabricante del grupo. Establecer la notación constructor se une la variable x y debe ser utilizado con el mismo cuidado aplicado a las variables vinculados por cuantificadores.

Ejemplos:

  • es un conjunto que sostiene los cuatro números 3, 7, 15, y 31.
  • es el conjunto de números naturales.
  • es el conjunto de números de contar.
  • es el conjunto de números enteros entre 1 y 100, ambos incluidos.
  • es el conjunto que contiene 'a', 'b' y 'c'.
  • es el conjunto,
  • es el conjunto de tal manera que y es mayor que 0 y menor que f.
  • es el conjunto de todos los números naturales, incluso,
  • es el conjunto de los números racionales, es decir, los números que se pueden escribir como la relación de dos números enteros.
  • Por lo tanto, por ejemplo,, etc. Como un ejemplo,

Las elipses significa que la interpretación más simple se debe aplicar para continuar la secuencia. Si ningún valor de terminación aparecerá a la derecha de las elipses entonces se considera la secuencia que se va sin límites.

El'' se lee como "tal que", y separa la lista de variables a la izquierda de la regla para asignar valores a las variables de la derecha. Muchas veces el Estado de derecho es un predicado de la lógica formal. Sin embargo, puede ser cualquier cosa que es clara para los lectores como prosa sencilla. A menos que se especifique la variable se cuantifica universalmente sobre la norma, lo que significa que se incluyen en el conjunto de todos los valores posibles de la variable para la cual la regla es verdadera. Cuando el significado es claro se puede omitir el'' y el Estado.

Cuando la norma es un predicado entonces conectores lógicos formales pueden ser utilizados dentro de la regla. Por ejemplo, el signo representa y, requiriendo ambas cláusulas a su izquierda ya la derecha de la misma para ser 'true'. Como otro ejemplo, el signo significa "existe" y que se conoce formalmente como la cuantificación existencial. A veces se dan varias reglas separados por una coma o punto y coma, en este caso tomamos las reglas en conjunto, es decir, se interpreta la coma o punto y coma para significar lo mismo que.

El signo denota pertenencia configurar, y se puede leer como "miembro" o informalmente como "en". En un predicado de una cláusula de la forma es verdadera o falsa, o cuando se utiliza como un medio de restricción que sólo puede ser uno de los valores 1, 2, o 3.

Cuando el dominio sobre el cual se define el conjunto ya está claro que no es necesario proporcionar dentro de la cláusula de la regla. Se podría decir algo como: "El universo de discurso puede ser tomado como el conjunto de los números reales, en los que no se especifican en el interior de la notación:" y luego escribir:

  • es el conjunto

En lugar de la forma más completa como se muestra en el ejemplo original dado anteriormente.

También se puede utilizar una expresión en la lista de variables. Por ejemplo:

  • es el conjunto de números enteros impares.
  • Crea un conjunto de pares, donde cada par pone un número entero en correspondencia con un número entero impar.
  • es el conjunto porque la expresión se evalúa como verdadero o falso dados los diversos números naturales.

Se conoce en la literatura a sólo colocar el dominio calificadores directamente en la lista de variables. Para el ejemplo anterior esto produciría:

  • es el conjunto,

Técnicamente esto generaría el conjunto como la expresión a la izquierda de la "de manera que" se evalúa como verdadera o falsa, pero a costa de introducir ambigüedad en nuestra notación fabricante del grupo que puede decidir en lugar de interpretar que esto significa que x tiene un cualificación adicional de ser un número real. Como otro ejemplo, considere:

Si la interpretación de ser un dominio calificador, entonces este es el juego, sin embargo, si la interpretación de ser una expresión, entonces este juego es. Estas ambigüedades pueden ser resueltos por convención, por ejemplo, mediante la renuncia la capacidad de poner el operador inclusión conjunto de expresiones variables. Otra convención para eliminar esta ambigüedad, que no nos obliga a reducir la riqueza de expresiones, es simplemente no usar calificativos de dominio en la lista de variables, pero en vez de ponerlos con los predicados de regla.

Cuando hacemos pruebas de que la razón de las normas precedentes, como se muestra en la siguiente sección, el método abreviado de dejar calificadores de dominio con las variables no es una opción, y no tenemos que poner rigurosamente calificadores de dominio en las normas precedentes que estamos operando en. Si no podemos obtener resultados falaces.

Los predicados equivalentes Builder significa conjuntos equivalentes

Supongamos que tenemos dos predicados tenemos la intención de utilizar como reglas para juegos de construcción, decimos estas dos predicados son y. Supongamos que no hemos añadido calificativos o expresiones adicionales a la lista de variables. Ahora, además, asumir que cualquier valor de x viene de un dominio definido por el conjunto, es decir. Ahora supongamos también que construimos dos conjuntos de estos predicados:

y,

Como ya hemos dicho que el dominio es que podría haber dejado fuera de la y. De hecho, dejamos de lado el calificativo entenderse en el próximo estado de cuenta. Tenga en cuenta también que podemos dar a la variable que se utiliza para construir el conjunto de cualquier nombre, ya que tenemos exceso aquí hemos construido los sets en contra y. Ahora tenemos un resultado interesante en el campo de la lógica matemática:

Aquí utilizamos los corchetes para fines de agrupación. Esto nos dice que si los dos predicados siempre tienen el mismo valor verdadero o falso dado el mismo argumento sobre el dominio, entonces las dos series T y S son las mismas. Además, a la inversa, si los dos conjuntos de T y S son idénticos, es decir, tienen los mismos elementos, a continuación, nuestros dos predicados siempre producir el mismo valor lógico para el mismo argumento sobre el dominio de U. El uso de los dos puntos aquí después de que el cuantificador universal simplemente significa el cuantificador se aplica a lo que sigue. Tenga en cuenta este resultado es muy general que se aplica a cualquiera de esos conjuntos y predicados sobre cualquier dominio dado U.

La primera autora de este artículo wiki decidió declarar la equivalencia entre las series con predicados equivalentes teorema de la siguiente manera, tenga en cuenta que utiliza la abreviatura tanto ambigua de poner algunas eliminatorias simples con las variables, y prefiere utilizar un ':' en lugar de una barra vertical para 'tal que'. Este uso de los dos puntos no debe ser confundido con el uso de los dos puntos por encima de después del cuantificador universal que significa 'se aplican a'. Es para evitar tal confusión que muchos matemáticos prefieren la barra vertical para 'tal que':

Esto significa que dos conjuntos son iguales si y sólo si sus "requisitos de afiliación" son lógicamente equivalentes.

Por ejemplo, debido a que, para cualquier número real x, x2 = 1 si y sólo si | x | = 1, y, por lo tanto, ambas construcciones producen el mismo conjunto {-1,1}.

La paradoja de Russell

Que denota el conjunto de todos los conjuntos R S que no pertenecen a sí mismos. La inconsistencia de la existencia de este conjunto se conoce como la paradoja de Russell.

Las soluciones a la paradoja restringen la noción de conjunto de la construcción de algún modo. Para ilustrar esto en términos de la notación, vamos a X = P el conjunto de todos los elementos de un satisfactorio el predicado P. La restricción sobre la notación canónica fabricante del grupo afirma que X es un juego sólo si A ya se sabe que es un juego. Esta restricción está codificado en el esquema del axioma de la separación actual de la teoría axiomática de conjuntos estándar. Tenga en cuenta que este esquema del axioma excluye R desde sethood.

Variaciones

Términos más complicado que una sola variable

Otra variación en la notación de conjunto-constructor sustituye a los individuales variable x con una T término que puede incluir una o más variables, en combinación con las funciones que actúan sobre ellos. Así que en lugar de {x: F}, tendríamos {T: F}, donde T es un término que implica las variables x1 a xn. Por ejemplo:

  • {2n: n? N}, donde N es el conjunto de todos los números naturales, es el conjunto de todos los números incluso naturales.
  • {P/q: p, q? Z, q? 0}, donde Z es el conjunto de todos los números enteros, es el conjunto de todos los números racionales.

Z notación

En la notación de Z, el conjunto de todos los x que satisface la condición P sería escrito. En Z, pertenencia configurar un elemento de x se escribe en lugar de, la barra vertical se utiliza para indicar un predicado. Las versiones de la notación fabricante del grupo también están disponibles en Z que permiten condiciones más complicadas de una sola variable, usando una bala para indicar la forma de los miembros del conjunto. Así que denota el conjunto de todos los valores de F, donde x está en A y P sostiene.

Parallels en lenguajes de programación

Una anotación similares disponibles en varios lenguajes de programación es la comprensión de la lista, que combina mapas y operaciones de filtro sobre una o más listas.

En Python, los apoyos del set-constructor se reemplazan con corchetes, paréntesis o llaves, que da la lista, el generador y los objetos fijados, respectivamente. Python utiliza una sintaxis basada en Inglés. Haskell reemplaza llaves del set-constructor con corchetes y usos de símbolos, incluyendo la barra vertical set constructor estándar. Considere estos ejemplos dados en conjunto constructor de notación, Python, y Haskell:

La notación fabricante del grupo y la lista de notación comprensión son las dos instancias de una notación más general conocido como comprensiones mónada, que permite mapa/operaciones de filtros, como sobre cualquier mónada con un elemento cero.