BROWSE
ALPHABETICALLY
LEVEL:
Elementary
Advanced
Both
INCLUDE TOPICS:
Basic Math
Algebra
Analysis
Biography
Calculus
Comp Sci
Discrete
Economics
Foundations
Geometry
Graph Thry
History
Number Thry
Phys Sci
Statistics
Topology
Trigonometry
|
|
predicate calculus – set
predicate calculus
A system of symbolic logic which augments the propositional calculus with quantification over variables. The two forms of quantification are existential and universal, and are denoted by
respectively. This permits the construction of sentences such as
which could be read, “There exists an x such that for all y, x times y is equal to y.” (Such a sentence would be true in arithmetic or group theory, for instance.) When quantification is permitted only over variables, the logic is first-order. If quantification is permitted over classes of variables or over predicates, the logic is second-order.
proper class
A collection of elements that is not a set. For example, the collection of all sets must be thought of as a proper class in order to avoid the Russell paradox.
propositional calculus
The formal system of symbolic logic in which sentences are treated as objects related by the logical connectives:
The last two symbols are called the conditional and the biconditional respectively, but they are not essential; indeed all the connectives are fully expressible by the use of the two connectives for “or” and “not.” For example, “p implies q” may be equivalently expressed as “not p or q.” In the notation of propositional calculus, this equivalence may be written,
Cf. predicate calculus.
quantifier
See predicate calculus.
quasi-disjoint family
Set Theory: See D-system.
Quine atom
In set theory, a set whose only member is itself, i.e., x = { x }. More generally, some phrases may be “Quined” to form meaningful sentences, e.g., “is a five-word phrase” is a five-word phrase.
Ramsey cardinal
A cardinal k is called a Ramsey cardinal if
Cf. Ramsey’s Theorem.
Ramsey number
See Ramsey’s Theorem.
Ramsey’s Theorem
Graph theory: given any two positive integers m and n, there exists a number, called the Ramsey number of m and n, and denoted R(m, n), such that any simple graph with R(m, n) vertices either contains a clique with m vertices (all vertices adjacent) or an independent set with n vertices (no vertices adjacent).
The question of how to determine the Ramsey number for arbitrary m and n is unsolved and believed to be very difficult, but various lower and upper bounds on it have been proven over the years. In particular, it is known that R(m, m)  2m/2, and that R(m, n)  (m + n - 2)C(m - 1).
Also, certain specific Ramsey numbers are known, e.g., R(3, 3) = 6. Thus, in any group of six people, either three are mutual acquaintances or three are mutual strangers.
Set theory: Let n be a positive integer, k and l be (finite or transfinite) cardinals, and denote by k ln the assertion that the complete graph of size k in which each edge has been “colored” by one of n colors contains a complete subgraph of size l all of whose edges are the same color. More generally still, denote by
the assertion that if the subsets of k of size b have each been colored with one of a-many colors, then there is a subset of X of size l all of whose b-sized subsets are the same color (homogeneous). Ramsey’s Theorem (infinite case) may now be stated as: For all positive integers k and l, we have
i.e., for every coloring of the k-sized subsets of the natural numbers (w) into l colors, there is an infinite homogeneous set (an infinite collection of k-sized subsets all the same color).
This more general notion gives rise to a field of set theory known as Ramsey Theory, in which far more is known about infinite sets than finite ones.
real number
An element of the set R consisting of all of the rational numbers together with all of the irrational numbers. Sometimes called the continuum. Usually defined formally by a Dedekind cut of rational numbers. The real numbers form (uniquely) a complete ordered field, but are not algebraically complete.
It is a famous theorem of Georg Cantor that the real numbers are not countable.
Cf. complex number.
Related MiniText: Number -- What Is How Many?
real number line
A geometrical line graphically representing the set of real numbers, in which every real number corresponds to a unique point on the line, and every point on the line corresponds to a unique real number.
reflexive relation
A relation “ ~ ” on a set X is reflexive if for every element x in X we have x ~ x. The relation “ ~ ” is called irreflexive if for every x we have that x ~ x is false. Note that a relation may be neither reflexive nor irreflexive.
Cf. symmetric relation, transitive relation.
regular
Set Theory: An ordinal a is called regular if and only if it is a limit ordinal and the cofinality of a is a. All regular ordinals are cardinals. All successor cardinals are regular, but limit cardinals can fail to be regular. A cardinal which is not regular is called singular.
relation
An n-place relation is defined on a Cartesian product of n sets, and is represented by a set of ordered n-tuples. For example, the less-than (“<”) relation is a binary relation on numbers, and the membership relation (“e”) is a binary relation on sets. The property of forming a Pythagorean triple is a ternary relation on natural numbers, of which for example (3,4,5) is a member since 32 + 42 = 52.
In a binary (two-place) relation, the set from which the abscissae are taken is called the domain, and the set providing the ordinates is called the range. Binary relations are classified according to whether they are reflexive, transitive, and/or symmetric.
Cf. function, partial order, lattice.
relatively large
A set A of natural numbers is called relatively large if the number of elements of A is greater than the least element of A.
ring of sets
Given a set X, a ring on X is a collection of subsets of X which is closed under finite unions and set differences. If the ring includes X itself then it is an algebra of sets. If the ring is closed under countable unions, then it is called a s-ring.
Russell Paradox
(Bertrand Russell, 1901) A paradox of set theory which necessitated a more careful axiomatization of set theory in the 1920’s and 1930’s: Naively, some sets are members of themselves and some are not. For instance, the set of all apples is not itself an apple, but the set of all sets does seem to be a set. So consider the set X of all sets that are not members of themselves. We may ask, is X a member of itself? If it is then it cannot be, because of the way in which X itself was defined, but if it isn’t then it must be, by the same reasoning. Contradiction. The Russell paradox is resolved in modern set theory by a foundation axiom or axiom of regularity, and by limiting the “size” of objects we call sets. For example, the “set of all sets” is considered not to be a set but a proper class.
Schroeder-Bernstein Theorem
If there exists an injection from a set X into a set Y, and also an injection from Y into X, then there exists a bijection from X to Y, and hence X and Y have the same cardinality.
semi-lattice
A set with a single binary operation that is idempotent, commutative, and associative.
Cf. lattice.
sentential calculus
See propositional calculus.
set
Naively, any well-defined collection considered as a single, abstract object. By “well-defined” is meant that it is always possible to determine for a given set when something is an element of the set and when not. In formal set theory, the term “set” is not defined, but is a primitive term whose meaning is informed purely by the axioms in which it appears.
Cf. ZF, ZFC.
|
|
 
|