HOME
*





Counterexample
A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a counterexample to the generalization “students are lazy”, and both a counterexample to, and disproof of, the universal quantification “all students are lazy.” In mathematics, the term "counterexample" is also used (by a slight abuse) to refer to examples which illustrate the necessity of the full hypothesis of a theorem. This is most often done by considering a case where a part of the hypothesis is not satisfied and the conclusion of the theorem does not hold. In mathematics In mathematics, counterexamples are often used to prove the boundaries of possible theorems. By using counterexamples to show that certain conjectures are false, mathematical researchers can then avoid going down blind alleys and learn to modify conjectures t ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Witsenhausen's Counterexample
Witsenhausen's counterexample, shown in the figure below, is a deceptively simple toy problem in decentralized stochastic control. It was formulated by Hans Witsenhausen in 1968. It is a counterexample to a natural conjecture that one can generalize a key result of centralized linear–quadratic–Gaussian control systems—that in a system with linear dynamics, Gaussian disturbance, and quadratic cost, affine (linear) control laws are optimal—to decentralized systems. Witsenhausen constructed a two-stage linear quadratic Gaussian system where two decisions are made by decision makers with decentralized information and showed that for this system, there exist nonlinear control laws that outperform all linear laws. The problem of finding the optimal control law remains unsolved.Ho, Yu-Chi, "Review of the Witsenhausen problem". ''Proceedings of the 47th IEEE Conference on Decision and Control (CDC)'', pp. 1611–1613, 2008. Statement of the counterexample The statement of the co ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1995 by Andrew Wiles), have shaped much of mathematical history as new areas of mathematics are developed in order to prove them. Important examples Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers a, ''b'', and ''c'' can satisfy the equation ''a^n + b^n = c^n'' for any integer value of ''n'' greater than two. This theorem was first conjectured by Pierre de Fermat in 1637 in the margin of a copy of '' Arithmetica'', where he claimed that he had a proof that was too large to fit in the margin. The first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995, after 358 years of effort by mathe ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Seifert Conjecture
In mathematics, the Seifert conjecture states that every nonsingular, continuous vector field on the 3-sphere has a closed orbit. It is named after Herbert Seifert. In a 1950 paper, Seifert asked if such a vector field exists, but did not phrase non-existence as a conjecture. He also established the conjecture for perturbations of the Hopf fibration. The conjecture was disproven in 1974 by Paul Schweitzer, who exhibited a C^1 counterexample. Schweitzer's construction was then modified by Jenny Harrison in 1988 to make a C^ counterexample for some \delta > 0. The existence of smoother counterexamples remained an open question until 1993 when Krystyna Kuperberg constructed a very different C^\infty counterexample. Later this construction was shown to have real analytic and piecewise linear versions. References *V. Ginzburg and B. Gürel, A C^2-smooth counterexample to the Hamiltonian Seifert conjecture in R^4', Ann. of Math. (2) 158 (2003), no. 3, 953–976 * * * * *P. A. Sch ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Euler's Sum Of Powers Conjecture
Euler's conjecture is a disproved conjecture in mathematics related to Fermat's Last Theorem. It was proposed by Leonhard Euler in 1769. It states that for all integers and greater than 1, if the sum of many th powers of positive integers is itself a th power, then is greater than or equal to : : ⇒ The conjecture represents an attempt to generalize Fermat's Last Theorem, which is the special case : if , then . Although the conjecture holds for the case (which follows from Fermat's Last Theorem for the third powers), it was disproved for and . It is unknown whether the conjecture fails or holds for any value . Background Euler was aware of the equality involving sums of four fourth powers; this, however, is not a counterexample because no term is isolated on one side of the equation. He also provided a complete solution to the four cubes problem as in Plato's number or the taxicab number 1729. The general solution of the equation :x_1^3+x_2^3=x_3^3+x_4^3 is :x_1 = ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Tait's Conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by . The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian. The conjecture was significant, because if true, it would have implied the four color theorem: as Tait described, the four-color problem is equivalent to the problem of finding 3-edge-colorings of bridgeless ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Deductive Reasoning
Deductive reasoning is the mental process of drawing deductive inferences. An inference is deductively valid if its conclusion follows logically from its premises, i.e. if it is impossible for the premises to be true and the conclusion to be false. For example, the inference from the premises "all men are mortal" and "Socrates is a man" to the conclusion "Socrates is mortal" is deductively valid. An argument is ''sound'' if it is ''valid'' and all its premises are true. Some theorists define deduction in terms of the intentions of the author: they have to intend for the premises to offer deductive support to the conclusion. With the help of this modification, it is possible to distinguish valid from invalid deductive reasoning: it is invalid if the author's belief about the deductive support is false, but even invalid deductive reasoning is a form of deductive reasoning. Psychology is interested in deductive reasoning as a psychological process, i.e. how people ''actually'' draw ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Ganea Conjecture
Ganea's conjecture is a claim in algebraic topology, now disproved. It states that : \operatorname(X \times S^n)=\operatorname(X) +1 for all n>0, where \operatorname(X) is the Lusternik–Schnirelmann category of a topological space ''X'', and ''S''''n'' is the ''n''-dimensional sphere. The inequality : \operatorname(X \times Y) \le \operatorname(X) +\operatorname(Y) holds for any pair of spaces, X and Y. Furthermore, \operatorname(S^n)=1, for any sphere S^n, n>0. Thus, the conjecture amounts to \operatorname(X \times S^n)\ge\operatorname(X) +1. The conjecture was formulated by Tudor Ganea in 1971. Many particular cases of this conjecture were proved, till finally Norio Iwase gave a counterexample in 1998. In a follow-up paper from 2002, Iwase gave an even stronger counterexample, with ''X'' a closed, smooth manifold In mathematics, a differentiable manifold (also differential manifold) is a type of manifold that is locally similar enough to a vector space to allow ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Pólya Conjecture
In number theory, the Pólya conjecture (or Pólya's conjecture) stated that "most" (i.e., 50% or more) of the natural numbers less than any given number have an ''odd'' number of prime factors. The conjecture was set forth by the Hungarian mathematician George Pólya in 1919, and proved false in 1958 by C. Brian Haselgrove. Though mathematicians typically refer to this statement as the Pólya conjecture, Pólya never actually conjectured that the statement was true; rather, he showed that the truth of the statement would imply the Riemann hypothesis. For this reason, it is more accurately called "Pólya's problem". The size of the smallest counterexample is often used to demonstrate the fact that a conjecture can be true for many cases and still fail to hold in general, providing an illustration of the strong law of small numbers. Statement The Pólya conjecture states that for any ''n'' > 1, if the natural numbers less than or equal to ''n'' (excluding 0) are parti ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Hilbert's Fourteenth Problem
In mathematics, Hilbert's fourteenth problem, that is, number 14 of Hilbert's problems proposed in 1900, asks whether certain algebras are finitely generated. The setting is as follows: Assume that ''k'' is a field and let ''K'' be a subfield of the field of rational functions in ''n'' variables, :''k''(''x''1, ..., ''x''''n'' ) over ''k''. Consider now the ''k''-algebra ''R'' defined as the intersection : R:= K \cap k _1, \dots, x_n\ . Hilbert conjectured that all such algebras are finitely generated over ''k''. Some results were obtained confirming Hilbert's conjecture in special cases and for certain classes of rings (in particular the conjecture was proved unconditionally for ''n'' = 1 and ''n'' = 2 by Zariski in 1954). Then in 1959 Masayoshi Nagata found a counterexample to Hilbert's conjecture. The counterexample of Nagata is a suitably constructed ring of invariants for the action of a linear algebraic group. History The problem originally arose in algebraic invari ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Universal Quantification
In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other words, it is the predication of a property or relation to every member of the domain. It asserts that a predicate within the scope of a universal quantifier is true of every value of a predicate variable. It is usually denoted by the turned A (∀) logical operator symbol, which, when used together with a predicate variable, is called a universal quantifier ("", "", or sometimes by "" alone). Universal quantification is distinct from ''existential'' quantification ("there exists"), which only asserts that the property or relation holds for at least one member of the domain. Quantification in general is covered in the article on quantification (logic). The universal quantifier is encoded as in Unicode, and as \forall in LaTeX and relate ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mathematical Proof
A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation". Presenting many cases in which the statement holds is not enough for a proof, which must demonstrate that the statement is true in ''all'' possible cases. A proposition that has not been proved but is believed to be true is known as a conjecture, or a hypothesis if frequently used as an assumption for further mathematical work. Proofs employ logic expressed in mathematical symbols ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]