True. The logarithm identity givesFor , , so . By monotonicity of the natural logarithm, the expression lies between and . It is therefore in Big O notation.
True. Rationalizing the square root gives, for ,The uniform bound is exactly the assertion in Big O notation.
False. Set . For ,Iteration gives a growing geometric sequence as a lower bound for . Hence and no eventual constant can bound , as Big O notation would require.
Use mathematical induction with two consecutive base cases: and . Suppose the bounds hold for exponents and . The Fibonacci recurrence givesThus the consecutive pair of bounds advances one step. for every .
For each , surjectivity makes the fiber of a function nonempty. Choose one element of each such fiber of a function and define . Then for every , proving . For arbitrary sets, the simultaneous selection invokes the usual axiom of choice; this is the right-inverse characterization of the axiom of choice. For finite only finitely many choices are needed. If is empty, the unique empty function gives the same conclusion.
Suppose . Applying and using the right inverse identity givesThis is exactly injectivity, so every right inverse is injective.
Not injective; surjective. The equal values disprove injectivity. For any , take . This lies in the stated domain of a function, andConsequently every member of the codomain has a preimage.
Not injective; its image of a function is exactly . For example, both and give the ceiling function value . Since , , so the value is never attained. For every positive integer ,Each such interval is nonempty and contained in , with the upper endpoint excluded when . Thus the answer concerning surjectivity depends on the convention for the natural numbers: onto if , and not onto if . The source does not settle that convention.
Both injective and surjective. The natural logarithm is strictly increasing on the positive real numbers, so it is injective. For every , satisfies ; hence the function is surjective, with the exponential function as its inverse function.
Not injective; surjective. Indeed, although . This polynomial is continuous, with as and as . For any prescribed real , choose with ; the intermediate value theorem supplies a preimage between and .
A function is injective if, for all , implies . Thus distinct elements of the domain of a function have distinct images.
Let abbreviate the universal premise, and put . The constants need not denote distinct elements. Use a fresh witness for the existential, then the justified three-case disjunction elimination from (i):
1 ∀x (x=c0 ∨ x=c1 ∨ x=c2) premise H
2 | ¬Q(c0) assume
3 | | ∃x Q(x) assume
4 | | | Q(u) fresh witness for 3
5 | | | u=c0 ∨ u=c1 ∨ u=c2 ∀-elim, 1
6 | | | | u=c0 first case
7 | | | | Q(c0) =-elim, 6 and 4
8 | | | | ⊥ ¬-elim, 7 and 2
9 | | | | K ⊥-elim, 8
10 | | | | u=c1 second case
11 | | | | Q(c1) =-elim, 10 and 4
12 | | | | K ∨-intro-L, 11
13 | | | | u=c2 third case
14 | | | | Q(c2) =-elim, 13 and 4
15 | | | | K ∨-intro-R, 14
16 | | | K 3-cases, 5, subproofs 6–9, 10–12, 13–15
17 | | K ∃-elim, 3, subproof 4–16
18 | (∃x Q(x)) → K →-intro, discharge 3–17
19 ¬Q(c0) → ((∃x Q(x)) → K) →-intro, discharge 2–18Equality elimination rule has exactly the forward orientation displayed in Figure 4: substitute the equal constant for in . At line 17 the fresh witness is absent from , and the remaining assumption. This proves the required sequent without assuming that the universe has exactly three distinct objects.
Expand three cases as two applications of disjunction elimination rule. For the association , the first outer branch assumes and applies the given and subproofs to obtain . The other outer branch is the given subproof. In schematic natural deduction form:
1 (φ ∨ ψ) ∨ ρ given
2 | φ ∨ ψ first outer case
3 | | φ first inner case
4 | | κ given φ-subproof
5 | | ψ second inner case
6 | | κ given ψ-subproof
7 | κ ∨-elim, 2, cases 3–4 and 5–6
8 | ρ second outer case
9 | κ given ρ-subproof
10 κ ∨-elim, 1, cases 2–7 and 8–9All three case assumptions are discharged and common surrounding assumptions remain. If the original three-way logical disjunction is parsed as , use the subproof as the first outer branch and eliminate inside the second. Thus either binary association has the asserted three-case disjunction elimination, without presupposing an unproved associativity.
The logical implication associates to the right. Assume its two antecedents, then use nested applications of the disjunction elimination rule.
1 | P ∨ Q assume
2 | | P ∨ ¬Q assume
3 | | | P first case of 1
4 | | | P available from 3
5 | | | Q second case of 1
6 | | | | P first case of 2
7 | | | | P available from 6
8 | | | | ¬Q second case of 2
9 | | | | ⊥ ¬-elim, 5 and 8
10 | | | | P ⊥-elim, 9
11 | | | P ∨-elim, 2, cases 6–7 and 8–10
12 | | P ∨-elim, 1, cases 3–4 and 5–11
13 | (P ∨ ¬Q) → P →-intro, discharge 2–12
14 (P ∨ Q) → ((P ∨ ¬Q) → P) →-intro, discharge 1–13This proof uses logical falsity elimination rule, but does not need law of excluded middle or double-negation elimination.
Retain the two given logical implications and temporarily assume their common starting proposition.
1 P → Q premise
2 Q → R premise
3 | P assume
4 | Q →-elim, 3 and 1
5 | R →-elim, 4 and 2
6 P → R →-intro, discharge 3–5Only the original premises remain undischarged, giving the required composition of logical implications.
The iteration matrix has eigenvalues : expanding its characteristic polynomial down the first column leaves the triangular two-by-two block with diagonal entries . The distinct eigenvalues ensure diagonalizability. Thus its spectral radius is .
The previous bound gives , so the Gauss-Seidel iteration converges for every initial guess under the stated diagonalization. Its limit is the exact solution . Since , a fixed matrix also sends this transformed error to zero; its operator norm can account for any amplification in the original coordinates.
There are unlisted articles, also show them or only show them.