Suppose first that . Choose and so that for . There are only finitely many natural numbers below . Because at each of them, all ratios in this finite prefix are finite. Let
Then both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.
Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.
For real-valued functions, use magnitude comparisons. The constants below are independent of .
The statement in Big O notation means that some and integer satisfy for all . The statement in big omega notation means that some and satisfy for all .
Finally, in big theta notation means that some and satisfy
Equivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.
Pad every integer from through with leading zeros to obtain a unique six-digit decimal string. If its digits sum to , each digit is automatically at most , so the usual digit upper bound adds no restriction. We therefore count the nonnegative integer solutions of
By stars and bars, there are . The all-zero string is not counted because its digit sum is zero, so every counted integer is positive. Thus the answer is .
An allocation is a tuple of nonnegative integers with , where is the number in labelled box . Empty boxes are allowed. Encode the allocation by stars and bars: put stars before the first bar, between the first two bars, and so on. Adjacent bars represent an empty intermediate box; a bar at an end represents an empty end box.
Reading the group sizes recovers exactly one allocation from every such string, so this is a bijection. There are positions and we choose the bar positions. Hence stars and bars gives
No extra factor for ordering the objects is present, because the objects are indistinguishable. For the string has no bars and gives the single allocation of all objects to that box; for all boxes are empty, also a single allocation.
The rule of product says that if a construction has stages, with exactly choices at stage after every permitted earlier history, then it has possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.
For a permutation of distinct objects, choose the first object in ways, the second in ways, and continue until only one remains. Thus the number is
Every ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For , the unique empty arrangement agrees with .
Let and be the finite sets of objects satisfying the two properties. The rule of sum says that mutually exclusive alternatives have additive counts: if , then . Without disjointness, the corresponding inclusion-exclusion principle is
The rule of subtraction counts objects satisfying the first property but not the second:
In particular, if the objects with the second property form a subset of those with the first, the count is . These conditions prevent either double counting an overlap or subtracting objects that were not counted initially.
The printed expression has one unmatched closing parenthesis. Remove that final surplus parenthesis and read the first disjunct as ; the other disjunct has outer universal quantification over the displayed implication. To distinguish the two independent bound uses of , rename the first to .
Push the outer negation through the logical disjunction and through the quantifiers. Negating the implication preserves its existential antecedent and negates its consequent. Applying De Morgan's laws and the quantifier negation rules gives the negation normal form
Each negation is now directly before an atomic formula. No bound variable has been captured, and no original existential quantification in the antecedent has accidentally been negated twice.
Two unary predicates suffice. Require all four unary predicate types to be inhabited:
There are no constants, no logical equality and no nonunary predicates. Any two of these conditions disagree on at least one predicate, so one domain element cannot witness both. Hence every satisfying first-order structure has at least four elements, by distinct witnesses from incompatible unary predicates. Conversely take domain , and : the four elements realize the four displayed unary predicate types, respectively. These element names describe the example; they are not constants in the first-order sentence.
Use the intended first-order structure of real arithmetic, with Int selecting the integers; is the parameter in . A suitable first-order formula is
The first condition requires a real square root of . The second excludes every representation as a rational number with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular, is written and there is no extra division symbol. A square root exists exactly when , and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on does not affect the claim about the principal square root. At the formula is false; for there is no real witness. The meanings of and as real arithmetic, not just the meaning of Int, are part of this interpretation.
Combine a minimum with an adjacent pair in a linear order:
In , choose . The minimum and the adjacent pair in a linear order both exist. In , the dense order property rules out such an adjacent pair. In , adjacent pairs exist, but no minimum exists: for any , the integer is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.
Figure 1.
A minimum and an adjacent pair distinguish the two-interval order from a closed interval and the integers
. Orange highlights the consecutive domain members and in the two-interval order. The dotted arrow crosses points absent from that domain. A closed real interval has intervening domain members; the integers have adjacent pairs but no minimum. Details.
Express that the order is a dense order:
In either real interval, lies strictly between any two distinct ordered elements and remains in the domain. In the integers, have no intervening integer, so this first-order sentence is false. The endpoints of a closed interval do not prevent a dense order.
Express existence of a minimum using only the given strict-order relation:
In the closed interval , the witness is . In the open interval , every possible witness has the smaller member , so the first-order sentence is false. These witnesses are explanations in the ambient real numbers, not additional symbols in the first-order signature.
Only requires a natural deduction proof. Assume . Within that assumption, temporarily assume . By disjunction introduction, obtain ; applying by the implication elimination rule gives . Discharge by the implication introduction rule to derive . Disjunction introduction now gives . Finally discharge by the implication introduction rule:
All temporary assumptions are discharged. No classical rule is needed; the same proof works in Intuitionistic propositional logic. The false propositional formula has no proof in this sound natural deduction system.
Let and , so the two displayed propositional formulas are and . Their complete truth tables are
Therefore is a tautology; is not. For example makes the antecedent true via , while is false because is true and is false. This explains why having just one of the two logical implications is insufficient for the forward direction.
Use structural induction on the propositional formula. The induction claim is that its truth value under the all-one Boolean valuation is one. A variable has this truth value by definition. For the induction step, suppose the immediate subformulas each have truth value one. Then
These are all permitted construction cases. Thus every such propositional formula evaluates to one. Equivalently, the three logical connectives define one-preserving Boolean functions, and composition preserves this property. The variable-only base grammar matters: admitting a constant false formula would invalidate the claim.
The given logical implication is false exactly when and . For every literal on , there is such a false Boolean valuation making that literal true. For a prescribed value of or , give the other the same value and choose . For a prescribed value of or , give the other the opposite value and choose .
Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term , then every Boolean valuation satisfying would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.

There are unlisted articles, also show them or only show them.