Countable setIn mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.
Uncountable setIn mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers. There are many equivalent characterizations of uncountability. A set X is uncountable if and only if any of the following conditions hold: There is no injective function (hence no bijection) from X to the set of natural numbers.
Infinite setIn set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set that is directly required by the axioms to be infinite. The existence of any other infinite set can be proved in Zermelo–Fraenkel set theory (ZFC), but only by showing that it follows from the existence of the natural numbers.
Second-countable spaceIn topology, a second-countable space, also called a completely separable space, is a topological space whose topology has a countable base. More explicitly, a topological space is second-countable if there exists some countable collection of open subsets of such that any open subset of can be written as a union of elements of some subfamily of . A second-countable space is said to satisfy the second axiom of countability. Like other countability axioms, the property of being second-countable restricts the number of open sets that a space can have.
First-countable spaceIn topology, a branch of mathematics, a first-countable space is a topological space satisfying the "first axiom of countability". Specifically, a space is said to be first-countable if each point has a countable neighbourhood basis (local base). That is, for each point in there exists a sequence of neighbourhoods of such that for any neighbourhood of there exists an integer with contained in Since every neighborhood of any point contains an open neighborhood of that point, the neighbourhood basis can be chosen without loss of generality to consist of open neighborhoods.
SequenceIn mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called elements, or terms). The number of elements (possibly infinite) is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers (the positions of elements in the sequence) to the elements at each position.
Rational numberIn mathematics, a rational number is a number that can be expressed as the quotient or fraction \tfrac p q of two integers, a numerator p and a non-zero denominator q. For example, \tfrac{-3}{7} is a rational number, as is every integer (e.g., 5 = 5/1). The set of all rational numbers, also referred to as "the rationals", the field of rationals or the field of rational numbers is usually denoted by boldface Q, or blackboard bold \Q. A rational number is a real number.
Axiom of countable choiceThe axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function A with domain N (where N denotes the set of natural numbers) such that A(n) is a non-empty set for every n ∈ N, there exists a function f with domain N such that f(n) ∈ A(n) for every n ∈ N. The axiom of countable choice (ACω) is strictly weaker than the axiom of dependent choice (DC), which in turn is weaker than the axiom of choice (AC).
CardinalityIn mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set contains 3 elements, and therefore has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers.
Axiom of countabilityIn mathematics, an axiom of countability is a property of certain mathematical objects that asserts the existence of a countable set with certain properties. Without such an axiom, such a set might not provably exist.
BijectionIn mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set; there are no unpaired elements between the two sets. In mathematical terms, a bijective function f: X → Y is a one-to-one (injective) and onto (surjective) mapping of a set X to a set Y.
Countably compact spaceIn mathematics a topological space is called countably compact if every countable open cover has a finite subcover. A topological space X is called countably compact if it satisfies any of the following equivalent conditions: (1) Every countable open cover of X has a finite subcover. (2) Every infinite set A in X has an ω-accumulation point in X. (3) Every sequence in X has an accumulation point in X. (4) Every countable family of closed subsets of X with an empty intersection has a finite subfamily with an empty intersection.
Dedekind-infinite setIn mathematics, a set A is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.
Cardinal numberIn mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter (aleph) marked with subscript indicating their rank among the infinite cardinals. Cardinality is defined in terms of bijective functions.
Union (set theory)In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. A refers to a union of zero () sets and it is by definition equal to the empty set. For explanation of the symbols used in this article, refer to the table of mathematical symbols. The union of two sets A and B is the set of elements which are in A, in B, or in both A and B.
Dyadic rationalIn mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in computer science because they are the only ones with finite binary representations. Dyadic rationals also have applications in weights and measures, musical time signatures, and early mathematics education. They can accurately approximate any real number.
Bijection, injection and surjectionIn mathematics, injections, surjections, and bijections are classes of functions distinguished by the manner in which arguments (input expressions from the domain) and (output expressions from the codomain) are related or mapped to each other. A function maps elements from its domain to elements in its codomain. Given a function : The function is injective, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain.
Finite-state transducerA finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings.
First uncountable ordinalIn mathematics, the first uncountable ordinal, traditionally denoted by or sometimes by , is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum (least upper bound) of all countable ordinals. When considered as a set, the elements of are the countable ordinals (including finite ordinals), of which there are uncountably many. Like any ordinal number (in von Neumann's approach), is a well-ordered set, with set membership serving as the order relation. is a limit ordinal, i.
Coprime integersIn number theory, two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides a does not divide b, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also a is prime to b or a is coprime with b. The numbers 8 and 9 are coprime, despite the fact that neither considered individually is a prime number, since 1 is their only common divisor.
