I am busy latedays with "Logic and Structure" of Van Dalen in order to get some familiarity with logic.  Proposition symbols are introduced (on page 7) as members of an infinitely countable set $\{p_0,p_1,p_2,\dots\}$.  My first thought was: why not just a set without any further specification?  Uptil now I could not find a satisfying answer.  Let me mention that I did find a proof (on page 44) that every (syntactically) consistent set of propositions is contained in a set of propositions that is maximally consistent, and in that proof it is used that the set of proposition symbols is countable.  That however can also be proved if there is no countability, but then by application of the lemma of Zorn.  So I wondered if the countability is there because this (i.e. Zorn/axiom of choice) must be avoided for some reason.  I really don't know...  So my question is:     Is there a special reason/motivation to go for an (infinitely) countable set of proposition symbols?
121451
Every proof that I read seems to assume that $|L|\leq\aleph_0$. But then how do you model things like field over $\mathbb{R}$ without running out of variable symbols?  More importantly, how can I prove that $|L|\leq\aleph_0$?
2059
Looking at Tarki's semantics wrt First Order Logic, I have some problems in pinning down the true reason why, given an $L$-structure $M$, and any $L$-sentece $\sigma$ (atomic for simplicity), we have $$M \not\models \sigma \wedge \neg\sigma$$ In this context, structures are sets with given functions and relations that interpret their symbolic counterparts. Given the actual definition of "$\models$", everything boils down to the fact that the sets we are working with are well-behaved, in the sense that we cannot have $$a \in P \wedge a \not\in P$$ But then I ask myself why the reason behind this. Is it a "consistency" assumption we are making on these sets? And if these sets are described by ZF, are we assuming the consistency of ZF?   Thanks
95639
I understand how we can show the existence of a choice function for any (finite or infinite) collection of (finite or infinite) subsets of, say, $\mathbb{N}$ or $\mathbb{Z}$ without using the axiom of choice, by showing that a well-ordering over the union of sets in the collection exists.  What I don't see though is how to do the same for what appears to be a much simpler case: a (possibly infinite) collection of finite sets, where nothing else is said about the sets other than that each of them is finite.  I would need to show a well-ordering exists over the union of those sets, but since they were not explicitly defined to be subsets of $\mathbb{N}$ or $\mathbb{Z}$, I first need to show the following, for example:  (i) there exists a surjection from $\mathbb{N}$ to $\bigcup X_i$ for an arbitrary collection of finite sets $X_i$  Correct so far?   Alternatively, I'm on the wrong track, and this is precisely a case that (unintuitively for me then) requires application of the axiom.  If so, I suppose I don't see why (i) wouldn't hold, when it seems that any definition within ZF of a finite number of elements is equivalent (in some sense to be made precise) to a finite subset of $\mathbb{N}$, so, given that the union of a collection of finite subsets of $\mathbb{N}$ is a subset of $\mathbb{N}$, the required well-ordering exists.
116757
Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.  I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: .  The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.  My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?  My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.  Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?  Update: There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.  Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.
118524
I don't know if this is appropriate for math.stackexchange, or whether philosophy.stackexchange would have been a better bet, but I'll post it here because the content is somewhat technical.  In ZFC, we can prove that the (second-order) Peano axioms have a model, call it $\mathbb{N} = (N,0,S)$. Furthermore, $\mathbb{N}$ is unique up to isomorphism. Thus, it would seem that we've pinned down $\mathbb{N}$.  However, if ZFC is consistent, then it has some very peculiar models. In particular, it has a model $(V_0,\in_0)$ whose "native" $\mathbb{N}$, let call it $\mathbb{N}_0$, is a model for the sentence "ZFC is consistent," and another model $(V_1,\in_1)$ whose "native" $\mathbb{N}$, lets call it $\mathbb{N}_1$, is a model for the sentence "ZFC is inconsistent."  But in reality, in other words, for the "real" $\mathbb{N}$, only one of these can be sentences can be true. Furthermore, the objects $\mathbb{N}_0$ and $\mathbb{N}_1$ aren't isomorphic, since the set of sentences they satisfy are different.  So it seems to me that $\mathbb{N}$ cannot truly be pinned down. Furthermore, its categoricity is, in some sense, illusory. Is this correct, or am I missing something?
23683
Ever since day one of of my Mathematical Logic course, this fact has really bothered me. I cannot wrap my head around how an empty set is a subset of every possible set. Could someone kindly explain how this is true? Any help is appreciated!
48515
Dear Everyone on this Wonderful Sites:  I'm so glad to participate on this site and ask the first question that mentioned on the Contest some days ago. I ran into a question that wrote this set:   $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in  \mathbb{N}  \}$   and ask this question, Which of the following is False:     -)  this is Satisfiable      --) this is Complete      ---) this is Decidable      ----) set of logical result of this set is effectively enumerable.   Solution of answer sheet is (2).   We try to solve it that without any detail is mentioned in the contest. one of our TA says, It is satisfiable because the TFTF... will satisfy it.  (We couldent get it) and it is decidable because propositional logic is decidable. We read some useful website for completeness (--) and for (----), but we get stuck in it until yet. any useful hint or idea for this question will be highly appreciated.
92813
Here I offer a "proof" of why the power set of the natural numbers is countable by creating a supposed bijection. I know that my proof is wrong, but where? If anyone could point it out, that'd be awesome.  Consider the power set of the natural numbers. We can form a bijection $f:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ as follows.  For any $f(x)$ convert $x$ to its binary representation, which is a string of $0$s and $1$s. If the $i$-th digit is $1$, then include $i$ in the output set $S=f(x)$. Otherwise do not include $i$. Note that $i$ is $0$-indexed and starts from the right-most digit.  So in this case $f(5)=\{1,3\}$. Supposedly we can construct any set in $\mathcal{P}(\mathbb{N})$ with an appropriate choice of $x$.  Where does this proof blow up?
24436
Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can define a set $A^{*}=\left \{ \left. a, ksdjf, blocks, coffee, maskdj, \dots, asdlkajsdksjfs \right \} \right.$ (words) as a set that consists of all finite sequences of the elements/letters from our $A$/alphabet. My question is, is this set $A^{*}$ countably or uncountably infinite? Does it matter how many letters there are in your alphabet? If it was, say, $A=\left \{ \left. a \right \} \right.$, then the words in $A^{*}$ would be of form $a, aa, aaa, \dots$ which, I think, would allow a bijection $\mathbb{N} \to A^{*}$ where an integer would signify the number of a's in a word. Can something analogous be done with an alphabet that consists of 26 letters (Latin alphabet), or can countability/uncountability be proved otherwise? And as mentioned before, I am wondering if the number of elements in the alphabet matters, or if all it does is change the formula for a bijection.   P.S. Now that I think of it, maybe we could biject from $\underset{n}{\underbrace{\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\dots\times\mathbb{N}}}$ to some set of words $A^{*}$ whose alphabet $A$ has $n$ elements? Thanks!
100909
Possible Duplicate:          Those terms keep confusing me. Could somebody give a clear and unambiguous definition? How do we prove a set is countable, finite, ...? I know that there are more real numbers than there are integers. How do we prove this? What about other sets like $\mathbb{Z, Q, C}$?
78501
In Chiswell's Mathematical Logic, there is the following problem is posed using the language of propositions (LP):     In some systems of logic (mostly constructive systems where 'true' is taken to mean 'provable') there is a rule      if $(\Gamma\vdash(\phi\,\lor\psi))$ is a correct sequent then at least   one of $(\Gamma\vdash\phi)$ and $(\Gamma\vdash\psi)$ is also correct.      By giving a counterexample to a particular instance, show that this is   unacceptable as a rule for LP. [Start by giving counterexamples for   both the sequents $(\vdash p_0)$ and $(\vdash(\neg p_0))$.]   In my , it was answered that one can let $\Gamma = \{p_0\,\lor\,(\neg p_0)\}$.  From there, one can deduce neither $(\Gamma\vdash p_0)$ nor $(\Gamma\vdash (\neg p_0))$.  But this does not proceed by the counterexample route that the author suggests.  Namely, he seems to imply that we should (1) take an interpretation of propositional variables $p_0,\,p_1,\,\ldots$ (setting each one equal to T or F), and (2) write $\phi$ and $\psi$ as functions of these propositional variables, and (3) pick sentences for $\Gamma$ which are all T, all with the conditions that (A) $(\phi\,\lor\psi)$ is evaluated as T, yet (B) both $\phi$ and $\psi$ are evaluated as F.  This, of course, seems impossible.  What, then, am I missing?  It seems that taking a concrete interpretation of the propositional symbols makes the constructivist's rule irrefutable.  (Note: this is supposed to be a very simple problem set, and I am an elementary logician).
58696
Could someone verify my proofs?  Proposition: the set of all finite subsets of $\mathbb{N}$ is countable  Proof 1:  Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$.  We can have a function $g_{n}: \mathbb{N} \rightarrow A_{n} $ for each subset such that that function is surjective (by the fundamental theorem of arithmetic). Hence each subset $A_{n}$ is countable.   By the "Union of countable sets is countable" theorem, X is countable.  Q. E. D.  Proof 2: Suppose we have an ordered list of prime numbers $p_{1}, p_{2}, ..., p_{n}$. Define a function $g: X \rightarrow \mathbb{N}$  such that $ g(A) = (p_{1})^{a_{1}}*(p_{2})^{a_{2}}*...*(p_{k})^{a_{k}} $ with $k=$ number of elements of each subset and $ a_{1}, a_{2}, ..., a{k} $ the ordered elements of them. By the fundamental theorem of arithmetic, that function is injective, hence $X$ is countable.   Q. E. D.
66884
In naive set theory, I believe ∅ = {∅} = {{∅}} is correct, but just wanted to make sure that I understood this correctly.   ∅ is an empty set, so having an empty set as an element of a set that contains nothing else is pretty much the same thing as e.g. marking the number 2 as 2.000000, right? Doesn't the symbol ∅ intrinsically imply that this is an empty set which contains it self?
20559
This question was inspired by the question on .  From the discussion in the comments there, it seems there does not exist a set of all sets of a given cardinality.  To me, it seems easy to see that this is true for any nonzero finite cardinality $n$. Given any set $x$, you can always make a set of size $n$ by adding $n-1$ other sets to $x$ to make a set of size $n$, which exists by repeated use of the pairing axiom.   But how would you do this for infinite cardinalities? For suppose $\kappa$ is some given infinite cardinality. To show that the set of all sets of cardinality $\kappa$ does not exist, it seems you would have to show that for any set $x$, there exists a set of that size with $x$ as an element, and then you could take the union of that set to find the set of all sets, and thus a contradiction. But it doesn't seem reasonable to simply say, for a given set of size $\kappa$ if $x$ is in the set, we have no problem. If not, just take an element out of the set and put $x$ in. Something about that seems like it would not be allowed.  So how would you do this for infinite cardinalities?
123408
The proof that the set of real numbers is uncountably infinite is often concluded with a contradiction. In the following argument I use a similar proof by contradiction to show that the set of rational numbers can be shown to be uncontably infinite:  Let us assume that the set of rational numbers is countable. This implies that we can write all the rational numbers between 0 and 1 in a list. Let us say, it looks something like this:     $ 0.\color{red}0000000001000000...\\ 0.0\color{red}10000001110000...\\ 0.10\color{red}000001000000... \\ ....$   ans so on. Now, create a new number that picks $n^{th}$ digit from $n^{th}$ number and  changes it to $0$ if it is $1$ and vice versa.     $0.101.... $   This number, say $x$, is between 0 and 1, and so it must appear in the list. Suppose it appears at the $n^{th}$ position in the list. However, based on how we constructed $x$, we know that the $n^{th}$ digit of $x$ is different from the $n^{th}$ digit of the $n^{th}$ number in the list. So, $x$ should be different from the $n^{th}$ number in the list at the $n^{th}$ digit and hence, this is a contradiction. We can conclude that such a list of the rational numbers does not exist and hence, the set of rational numbers is uncontably infinite.  I know that there is another mapping between the set of rational numbers and natural numbers that can show that there is one-to-one mapping between the two sets (). However, the above proof in that sense is not really conclusive and that the set of real numbers might also be countably infinite and it is just that we are not yet aware of the mapping.  Please provide your comments if the above proof is somehow flawed for rational numbers or if I'm missing something.
122923
From $\mathrm{ZFC},$ define a new theory $\mathrm{ZFC}^E$ by adjoining a constant symbol $E$ together with axioms to the effect that:   $E$ is countable and transitive $(E,\in)$ is an elementarily equivalent to $(V,\in).^*$ (This is an axiom schema).   Question. Is $\mathrm{ZFC}^E$ outright inconsistent?  Motivation. The idea (or motivation) is to have a "miniature copy" of the universe available, that is nonetheless "very small" from our omniscient $V$-like perspective.
10824
Math people:  The title is the question. I am convinced that uncountable sets exist, thanks to Cantor's diagonal proof.  It is not intuitively clear to me that uncountable ordinals or cardinals should exist.  What axioms of set theory are needed to accept their existence?  I think I have read here that the Axiom of Choice is not necessary.  I am reluctant to accept as "true" any theorems that rely on the Axiom of Choice.  EDIT: This question may be a duplicate: I just found  .  I apologize if this is so.