New answers tagged

0

The formulation of Replacement in the book Set Theory:An Introduction to Independence Proofs, by K. Kunen,is different : When $f$ is a formula whose free variables are among $x,y,A,v_1,...,v_n$ then $$\forall A\;\forall_{j=1}^nv_i\;[\;\forall x\in A\;\exists! y\;(f) \implies \exists Y\;\forall x\in A\;\exists y\in Y\;(f)\;].$$ This is weaker than ...


2

There appears to be a typo in the last bit. Here's what I would write: If $a^2=1$, then - since we know that $ab=1$ - we have $a^2=ab$. So multiplying both sides by $a^{-1}$ we get $a=b$, a contradiction. I don't see how the author deduces $b=1$ here; I think "$1$" should be "$a$".


3

$a^2$ is an informal abbreviation for $a\cdot a$. As to your later question about $a^2\cdot a^{-1}$, it means $(a\cdot a)\cdot a^{-1}$. By associativity this is $a\cdot (a\cdot a^{-1})$, which is $a\cdot 1$, which is $a$.


0

The composition of functions is associative, $f(g(h(x))) = f(g(x))\circ h(x)$ is the same as $f(x)\circ g(h(x))=f(g(h(x)))$. For the second property, you are correct that they aren't always identical, $c(f\circ g)(x)=cf(g(x))$, whereas $c f(x) \circ cg(x)=cf(cg(x))$. Hence you can conclude that it isn't a vector space.


1

Well you could try calculating the RHS of that expression, $$cx+dx=c(x_1,x_2)+d(x_1,x_2)=(cx_1,cx_2)+(dx_1,dx_2)=(cx_1+2dx_1,3cx_2-2dx_2),$$ compare it with the LHS which is $$(c+d)x=(c+d)(x_1,x_2)=\big((c+d)x_1,(c+d)x_2\big).$$ Are they the same?


5

BrianO's answer is spot-on, but it seems to me you may not be too familiar with models and consistency proofs, so I'll try to provide a more complete explanation. If anything it may better steer you towards what you need to study, as admittedly I'm about to gloss over a lot of material. Why do we need the axiom of infinity? Because we know (and can prove) ...


1

The point is once you collect all the natural numbers into a set, you can now treat that set as an atomic object like any other and you can do all the things you can do with a set to it. So, for example, you can make a set that has the set of natural numbers as an element, you can construct the powerset of natural numbers, you can make functionals ...


6

The existence of each natural number follows from the other axioms of set theory, but if you drop the Axiom of Infinity (AxInfinity), the resulting theory ZFC-AxInfinity has a (transitive) model consisting of the hereditarily finite sets, which contains no infinite sets. The axioms of ZFC-AxInfinity provide no way to gather all the natural numbers into a ...


1

A good way to think of this is that although the axioms of ZFC are infinite in number, there is a computer program that prints them all out, one axiom per row. The "Separation Schema" is the primary subroutine which produces infinitely many axioms. What that subroutine does is to internally go through the infinitely many sentences having one free variable, ...


2

No, they're definitely definite. The axioms of ZF(C) are sentences. (Anyway, the result of binding any free variables in an axiom schema with universal quantifiers is a sentence; think of that as the axiom.) The comprehension axiom schema states that for every formula $\varphi(x)$ in the first order language of set theory, (the universal closure of) the ...


2

Set theory has a language, and this language has terms, formulas and sentences. Just like any other language in logic. The schemata in set theory simply give you a template, and they state that for every formula in the language we add an axiom which has a certain form. Remember that set theory does not happen in vacuum. It is formalized in first order ...


2

This is an instance of the soundness theorem (for first-order logic; there is an analogous soundness theorem for propositional logic, which it might be good at to look at first). The theorem states that if $T$ proves $\theta$, then $\theta$ is true in every model of $T$. The proof is by induction on the length of the proof, breaking into cases depending what ...


1

You have some boxes, at least one. There may be only one box, seven boxes, or infinitely many boxes. In each and every box, there are some items. at least one. There may be arbitrarily many items. Question: Can you pick, at least in principle, exactly one item from each box, without necessarily describing the details or rules of how you select them? The ...


-2

Hint: Along the lines of Hagen's answer, construct function $S$ such that: $$\forall a\in R: S(a)=a+1$$ Construct $N$ such that: $$\forall a:[a\in N \iff a\in R \land \forall b\subset R:[0 \in b \land \forall c\in b: [S(c)\in b] \implies a\in b]]$$ Then prove: $0\in N$ $\forall a\in N: S(a) \in N$ $\forall a,b \in N:[S(a)=S(b)\implies a=b]$ $\forall ...


3

There's no such thing as an 'undefined value', because if a value is undefined, then it isn't a value. When we say something is undefined, what we really mean is either that a written expression has no meaning, or that there are no objects with a certain property. Here, 'the last digit of $0.101010\dots{}$' is undefined, in the sense that $0.101010\dots$ ...


2

To have any hope of proving, in axiomatic set theory, that $S=\{\emptyset,s(\emptyset),s(s(\emptyset)),\dots\}$, you'd first have to express $\{\emptyset,s(\emptyset),s(s(\emptyset)),\dots\}$ in the language of axiomatic set theory. The difficulty here is the ellipsis "$\dots$". I don't see any way to define that without a prior notion of "natural number" ...


1

Every totally ordered field has characteristic $0$, hence contains an isomorphic copy of $\mathbb{Q}$ (which we can just identify with $\mathbb{Q}$). I guess you are comfortable with the fact that $\mathbb{N} \subset \mathbb{Q}$?


4

With $S\colon \Bbb R\to\Bbb R$, $x\mapsto x+1_{\Bbb R}$ let $\Bbb N$ be the intersection of all subsets of $\Bbb R$ that contain $1_{\Bbb R}$ and are closed under $S$. That is: With $e=1_{\Bbb R}$ (or $e=0_{\Bbb R}$ depending on taste) the definition $$\Phi(A)\stackrel {\text{def}}\iff e\in A\land \forall x\in A\colon S(x)\in A$$ we let $$\Bbb N\stackrel ...


0

Basically Theorems are based off of other proven statements such as Axioms or even other Theorems, and Axioms are kind of unchallenged rules and assumptions, such as simple addition equations.


0

One easy way to see this is false is that the $\sf ZF$ axioms prove that $\in$ is not transitive on every set. Namely, there exists $a,b,c$ such that $a\in b$ and $b\in c$, but $a\notin c$. For example, $a=\varnothing, b=\{\varnothing\}, c=\{\{\varnothing\}\}$. On the other hand, $<$ is transitive on $\Bbb Q$. (Another way, using far heavier guns, ...


1

You have to interpret $\in$ with $<$. In order to check whether extensionality holds you have to consider the sentence for all $x$ and $y$, $x=y$ if and only if, for every $z$, $z<x$ if and only if $z<y$ or, in symbolic form, $$ \forall x\forall y (x=y \leftrightarrow (\forall z(z<x\leftrightarrow z<y))) $$ where the universe is, of ...


5

The set $\rho(E) = \mathcal P (E)$ is the set of all the subsets of $E$, while $\Phi$ is a collection of subsets of $E$ (which may not contain all of them). In other words : $\Phi \subseteq \rho(E)$. For instance, if $E =\{1,2\}$, then the power set of $E$ is $\rho(E) = \{\varnothing, \{1\}, \{2\}, E\}$ and you can take $\Phi = \{\{2\}, E\}$ as a collection ...


5

Look at the function $f : \omega \to \omega + \omega$ defined by $f(n) = \omega + n$. This function is not a member of $V_{\omega + \omega}$, but it's definable using parameters from $V_{\omega + \omega}$, and its domain is in $V_{\omega + \omega}$. Its range is not a member of $V_{\omega + \omega}$. You can use this argument in more generality to show ...


0

If you consider the axioms of separation pairing and union, you can apply them to a finite set, $A$, to create a set of all subsets of $A$, called the powerset of $A$, notated as $\mathscr P(A)$. E.g. for $A = \{1, 2\}$ you can use separation to create the subsets $\emptyset, \{1\}, \{2\}, \{1, 2\}$. Then pairing to combine $\emptyset, \{1\}$ into $\{ ...


6

The answer is that you can't. Instead of omitting foundation, I'll add atoms. You can replace them by Quine atoms and have the same results without foundations to your liking. We construct the same permutation model as in this answer: start with a proper class of atoms and global choice, and make the class of atoms have only finite subsets while preserving ...


2

The power in the power set axiom is the ability to create larger sets than any other axiom is capable of. At least we want it because we probably want $\mathbb R$ (to be a set). The other axioms doesn't seem to be strong enough to guarantee the existence such large set (larger than $\mathbb N$). Note that dropping an axiom would not make it ...


0

The power set axiom is used to construct Cartesian products, which are used for relations, which are used for defining "function." See https://en.wikipedia.org/wiki/Axiom_of_power_set at least for Cartesian products.


8

With your definition of "infinite set" (which is Dedekind's definition, not the usual one), no axioms beyond ZF are needed to prove that $\aleph_0$ is the smallest infinite cardinal. Let $A$ be an infinite set, and let $\phi:A\to A$ be an injection which is not a bijection. Choose an element $a\in A\setminus\phi(A).$ Then ...


6

The "most natural axiom" to add is perhaps the axiom of countable choice which asserts the existence of a choice function for every countable family of non-empty sets. I'd even argue that the true "natural axiom" would be the principle of dependent choice, which is a slight (but significant) strengthening of countable choice which posits that recursive ...


5

You can indeed adopt the axiom "every infinite set has a countably infinite subset", i.e., "every set that is not equipotent to a natural number (=finite ordinal) has a subset equipotent to the set $\omega = \mathbb{N}$ of natural numbers". This can also be reformulated as "every D-finite set is finite", where a D[edekind]-finite set is one that does not ...


1

There are two main issues here: Choice of formal system Meaning and truth Choice of formal system First you have to choose a logical system.$\def\imp{\rightarrow}$$\def\eq{\leftrightarrow}$ The conventional choice is classical first-order logic, which has boolean operations $\neg,\land,\lor,\imp,\eq$ (not,and,or,if-then,equivalent) and quantifiers ...


1

The easiest example is modular arithmetic, which is where you violate a Peano axiom by making your numbers wrap around, as on a clock. So in the ring of integers modulo $12$, the product $5\cdot 11$ is still well-defined but it is not $55$ but instead $7$. You can view this if you like as the remainder after division by $12$; $55$ is $4\cdot12 + 7$. ...


1

The transformation $$ (\exists x)(\forall y) \phi(x,y) \Longrightarrow (\forall f)(\exists x)\phi(x, f(x)) $$ is a special case of a process called Herbrandization. This is dual to the more well known operation of Skolemization. Indeed, if you know what Skolemization is then Herbrandization can be defined as the negation of the Skolemization of the negation ...


1

The dual of this (particularly in the context of automated theorem-proving), which results in a $\exists\forall$ formula is called Skolemization or conversion to Skolem Normal form. As pointed out in a comment, the formulation as in the question that leads to $\forall\exists$ formula is often called Herbrandization. I find Skolemisation more intuitive than ...


4

Consider the dual statement: $$ \forall x \exists y\, R(x,y) \iff \exists f \forall x\, R(x, f(x)). $$ (I've used more typical variables in stating it; no good purpose is served by using "$y$" as a variable for two different sorts of things.) This is essentially the Axiom of Choice (AC), and is provable using AC. $f$ is called a uniformizing function for ...


1

I believe Morse-Kelly set theory may satisfy your requirements. While it shares some axioms with ZFC, each theory contains axioms that the other does not, so MK is not simply ZFC + some other axiom, and MK is a second-order theory (sets and classes) while ZFC is only first-order (just sets). Most importantly MK is a proper extension of ZFC, in other words ...


2

Let P be a proposition which is independent of ZFC, and for each axiom A of ZFC, replace it with "A and P". It's not what you want, but I don't think you're going to be able to formulate a very well-defined question for what you want.



Top 50 recent answers are included