Tagged Questions

This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, (un)...

4k views

Need help with Recursion Theorem (Set Theory)

The recursion theorem In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem ...
658 views

Hyperreal measure?

If AC be accepted, then there exists a Lebesgue unmeasurable set called Vitali Set. However, I'm curious about measure valued in hyperreal numbers. Argument in disproof of unmeasurability of Vitali ...
7k views

Bijection from $\mathbb R$ to $\mathbb {R^N}$

How does one create an explicit bijection from the reals to the set of all sequences of reals? I know how to make a bijection from $\mathbb R$ to $\mathbb {R \times R}$. I have an idea but I am not ...
5k views

The Cantor set is homeomorphic to infinite product of $\{0,1\}$ with itself - cylinder basis - and it topology

I know the Cantor set probably comes up in homework questions all the time but I didn't find many clues - that I understood at least. I am, for a homework problem, supposed to show that the Cantor ...
6k views

A finite set always has a maximum and a minimum.

I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.
939 views

What is the name of the $\in$ symbol and where does it come from?

It looks like a lower-case epsilon, but the Wikipedia page on epsilon states that they are not the same. Does this symbol have a typographic identification outside of mathematics? Where did the ...
2k views

Subset of a finite set is finite

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$. How can we prove that a subset of a finite set is finite? It is ...
2k views

Why does Cantor's diagonal argument not work for rational numbers?

If we map every integer to a string that represents a rational number, and produce a number different from all the ones listed, we are essentially following Cantor's algorithm. But why does it not ...
281 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
406 views

Natural uses for the co-product of sets?

I had come across countless uses of the (Cartesian) product of sets long before I first ever met the concept of a "co-product"1 of sets. In fact, anyone who has learned basic analytic geometry in ...
202 views

A Question regarding disjoint dense sets

If we take the standard topology on $\mathbb{R}$ we can easily find two disjoint sets that are dense, namely $\mathbb{R}\setminus\mathbb{Q}$ and $\mathbb{Q}$. Similarily, if we take the same topology ...
16k views

Mathematical notation for the maximum of a set of function values

I have a question about the proper notation of the following (simplified) example: I want to express that I have a value alpha, which is the maximum of a set of n values. Each value in the set is the ...
Using set notation, define the set of even natural numbers between 100 and 500. This is what I have so far: $P$ is even numbers so the set of natural numbers between 100 and 500 would be $$P = \{x:... 6answers 1k views Is there a notation for being “a finite subset of”? I would gladly use a notation for "A is a finite subset of B", like$$A\sqsubset B \text{ or } A\underset{fin}{\subset} B,$$but I have never seen a notation for that. Are there any? While ... 7answers 2k views Is 1 a subset of \{1\} Is the number 1 a subset of the set \{1\} just as \{1\} is a subset of the set \{\{1\}\}? I'm a little bit confused because 1 is an element not a ... 5answers 1k views A \in B vs. A \subset B for proofs I have to prove a few different statements. The first is if A \subset B and B \subset C then prove A \subset C. This one is fairly straight forward, but I'm stuck on how the next one differs. ... 5answers 668 views Prove that every set with more than one element has a permutation without fixed points I cannot prove this statement so need help. This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal ... 2answers 4k views Which symbol should be used for an empty set? Currently, a discussion started on the German Wikipedia article for Empty Set (the German discussion), whether \emptyset or \varnothing should be used or is more common as a symbol for an empty ... 2answers 1k views Why is there this strange contradiction between the language of logic and that of set theory? In standard probability theory events are represented by sets consisting of elementary events. Consider two events for which (as sets) A \subset B. If an elementary event x \in A takes places then ... 5answers 1k views What is the meaning of set-theoretic notation {}=0 and {{}}=1? I'm told by very intelligent set-theorists that 0={} and 1={{}}. First and foremost I'm not saying that this is false, I'm just a pretty dumb and stupid fellow who can't handle this concept in his ... 3answers 1k views Why is cardinality of set of even numbers = set of whole numbers? I recently watched a YouTube video on Banach-Tarski theorem (or, paradox). In it, the presenter builds the proof of the theorem on the basis of a non-intuitve assertion that there as as many even ... 4answers 1k views How does the axiom of regularity forbid self containing sets? The axiom of regularity basically says that a set must be disjoint from at least one element. I have heard this disproves self containing sets. I see how it could prevent A=\{A\}, but it would seem ... 4answers 5k views Understanding equivalence class, equivalence relation, partition Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ... 4answers 578 views Looking for a problem where one could use a cardinality argument to find a solution. I would like to find an exercise of the type: Find some x in A\setminus B. Solution: since A is uncountable and B is countable such x exists... 1answer 336 views In naive set theory ∅ = {∅} = {{∅}}? 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 ... 5answers 1k views Dependence of Axioms of Equivalence Relation? This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 a \sim a Prop 2 a \sim b ... 4answers 4k views Empty intersection and empty union If A_\alpha are subsets of a set S then \bigcup_{\alpha \in I}A_\alpha = "all x \in S so that x is in at least one A_\alpha" \bigcap_{\alpha \in I} A_\alpha = "all x \in S so that ... 6answers 905 views Naive set theory question on “=” So I picked up a couple of good undergraduate-level books over the weekend and have been working through them... In Algebra: Chapter 0, the author of the text writes: The prototype of the well-... 5answers 16k views Is the void set (∅) a proper subset of every set ? I am a bit confused about the concept of proper subsets,precisely whether to include one or both of the void set and the set itself. An extract from my module goes like this : Obviously,every set is ... 3answers 3k views Cardinality of the set of prime numbers It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ? Cantor showed that the sets \mathbb{Q} and \mathbb{Z} have the same ... 3answers 693 views How to prove that from “Every infinite cardinal satisfies a^2=a” we can prove that b+c=bc for any two infinite cardinals b,c? Prove that if a^2=a for each infinite cardinal a then b + c = bc for any two infinite cardinals b,c. I tried b+c=(b+c)^2=b^2+2bc+c^2=b+2bc+c, but then I'm stuck there. 4answers 368 views A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ? 4answers 3k views When do two functions become equal? When do two functions become equal? I have stumbled over this definition of equality of functions in elementary real analysis. Let X and Y be two sets. Let f:X\rightarrow Y and g:X\... 2answers 270 views Characterization properties of number sets \mathbb{N},\mathbb{ Z},\mathbb{Q},\mathbb{R},\mathbb{C} When people say that a structure is defined up to isomorphism means, accordingly, that they assume certain properties that make it completely determined under certain operations and relations. So,... 4answers 3k views Examples of transfinite induction I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK. 4answers 2k views Difference between a function and a graph of a function? Formally, I learned that a function f: X \to Y is a subset f \subset X \times Y subject to the condition that for every x \in X, there is exactly one y \in Y such that (x, y) \in f. We write ... 6answers 1k views The simplest way of proving that |\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c What is the simplest way of proving (to a non-mathematician) that the power set of the set of natural numbers has the same cardinality as the set of the real numbers, i.e. how to construct a bijection ... 3answers 4k views limit inferior and superior for sets vs real numbers I am looking for an intuitive explanation of \liminf and \limsup for sequence of sets and how it corresponds to \liminf and \limsup for sets of real numbers. I researched online but cannot ... 2answers 87 views Does there exist a function g\in \mathbb{N}^\mathbb{N} s.t. \{f\mid f\circ f=g\} is not empty and finite? I'm struggling with this question and can't figure it out. The question was too long for the title so I will write it once more: Does there exist a function g : \mathbb{N} \longrightarrow \mathbb{N}... 3answers 508 views Why is the collection of all algebraic extensions of F not a set? When proving that every field has an algebraic closure, you have to be careful. In this article https://proofwiki.org/wiki/Field_has_Algebraic_Closure, and as I have been told on this site, if we have ... 4answers 2k views Is there a shorthand notation for adding an element to a set? I know that if you want to refer to the set  A  with the element  x  added, you can write  A \cup \{x\} . But is there a common shorthand for this? 4answers 857 views How does one get the formula for this bijection from \mathbb{N}\times\mathbb{N} onto \mathbb{N}? When showing that \mathbb{N}\times\mathbb{N} is in bijection with \mathbb{N}, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in \... 4answers 201 views How find this minimum of the value f(1)+f(2)+\cdots+f(100) Give the positive integer set A=\{1,2,3,\cdots,100\}, and define function f:A\to A and (1):such for any 1\le i\le 99,have$$|f(i)-f(i+1)|\le 1$$(2): for any 1\le i\le 100,have$$f(f(i))=100$... 2answers 269 views Problem about subsets of$\{1, 2,\dots,n\}$Let$A=\{1, 2,\dots,n\}$What is the maximum possible number of subsets of$A$with the property that any two of them have exactly one element in common ? I strongly suspect the answer is$n$, but ... 1answer 227 views Is there any connection between the symbol$\supset$when it means implication and its meaning as superset? [duplicate] A rather old-fashioned symbol for logical implication is$\supset$(see list of logic symbols). For example$p \supset q$means$p \implies q$or$p \rightarrow q$in more recent notations. Is there ... 1answer 168 views Coloring of positive integers Suppose$f:\mathbb{Z}^+\longrightarrow X$is a function, with$X$a finite set. Is it true that there are$a,b\in\mathbb{Z}^+$such that$f(a)=f(b)=f(a+b)$. 2answers 175 views Showing that$|A\cap B|/|A \cup B| + |B\cap C|/|B \cup C| - |A\cap C|/|A \cup C| \leq 1$for finite sets$A,B,C$. If$A$,$B$and$C$are finite sets, prove that $$\frac{|A\cap B|}{|A \cup B|} + \frac{|B\cap C|}{|B \cup C|} - \frac{|A\cap C|}{|A \cup C|} \leq 1.$$ It seem's simple, but I tried it for a ... 1answer 183 views Analogue of the term 'summand' for unions and intersections. If we have a sum$\sum\limits_{i=1}^na_i$, we call the terms$a_i$summands. In fact, in the cases of addition, subtraction, multiplication, and division, we have a large vocabulary to describe the ... 0answers 208 views Can$[0,1]$be partitioned into an uncountable union of uncountable sets? [duplicate] I was thinking about this:$[0,1]$can be partitioned into a countable union of uncountable sets. Write$[0,1]=(0,1]\cup \{0\}:$$$(0,1]=\bigcup_{n=1}^{\infty}\Big(\frac{1}{n+1},\frac{1}{n}\Big]$$$...
I do not even know if the question makes sense. The point is rather simply. If I have the sum of all natural numbers, $$\sum_{n\in \mathbb{N}}n$$ this is clearly "equal to infinity". But since ...