This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

0
votes
2answers
55 views

Is this proof of uncountability of Cantor set true?

To construct Cantor set $C$, start with $I_1=[0,1]$ and define $$E_1=\{0,1\}=\{x:x\text{ is an end point of the set }I_1\}.$$ $\operatorname{card}(E)=\#(E)=2$. After deleting the middle open interval ...
7
votes
5answers
469 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
1
vote
2answers
33 views

Proof of the description of a set

We are supposed to describe the set $\bigcup_{n=1}^\infty A_n$ with a proof. $A_n = \{(x, y) \in \mathbb{R}^2 | y-x^{2n} \geq 0 \}$. This is what I have so far: "This is just the set of all points ...
1
vote
1answer
26 views

What can we say about the set X?

We have a certain set $X$ for which is valid: $\forall U\subset X:[ U\neq X ]\rightarrow U\nsim X$. What can we say about $X$? I think we've got to use the axiom of choice here. My first guess would ...
0
votes
1answer
27 views

Cantor's theorem.

If $A$ is a infinite set then the power set of $A$, $\mathcal{P}(A)$, is an uncountable set. To proof first I take $A$ countable, and I suppose $\mathcal{P}(A)$ is countable, i.e., ...
0
votes
2answers
34 views

Is there an uncountable set S, a subset of P(N), such that for any A,B an element of S; the intersection of A and B is finite? [duplicate]

I have a feeling no such uncountable set exists but have no idea how I could formulate a proof to show this. If such an uncountable set did exist I could try and use a form of the diagonalization ...
1
vote
1answer
32 views

Proving that $x \not\in B \cap C \iff x \not\in B \lor x \not\in C$.

I've got a set theory question. I'm required to show that $x \not\in B \cap C$ if and only if $x \not\in B$ or $x \not\in C$. I decided to call the universal set $S$ (which contains both and $B$ and ...
0
votes
1answer
23 views

Set notation check

Are the three statements: $(a,b,c)\in\mathbb{Q}^3$ $\{a,b,c\}\subset\mathbb{Q}$ $a,b,c \in\mathbb{Q}$ equivalent ways of saying that a, b and c are rational numbers?
1
vote
1answer
27 views

Cantor Pairing Function [on hold]

I know that: $J(m,n)=\frac{(m+n)^{2}+m+n}{2}$. Is the Cantor pairing function that gives me a bijection between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$. But how can I show the Cantor ...
3
votes
2answers
48 views

Opposite of a function being bijective?

A function is bijective if it is both surjective and injective. Is there a term for when a function is both not surjective and not injective?
0
votes
2answers
22 views

Can a surjective function have an element in the domain not mapped to the codomain?

I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to ...
3
votes
0answers
18 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
2answers
59 views

Suppose A and B are finite sets and $f : A \rightarrow B$ is surjective. Is it possible that |A| < |B|?

I am trying to understand better what surjective functions is from a set $A$ to a set $B$, and from what I understood, it basically means this: A function is subjective (onto) from set $A$ to set ...
0
votes
1answer
21 views

Is $A∩B^c∩C^c = A-[A∩(B∪C)] $ ? (Set Theory)

I'm studying set operations. The example problem is: Find a simpler expression of $[(A∪B)∩(A∪C)∩(B^c∩C^c)]$ assuming all three sets intersect. The answer I came up with is $A∩B^c∩C^c$, while the ...
0
votes
2answers
44 views

can the empty set be an element of a group?

is the following group legal: $x = \{1,2,\emptyset\}$? If so, is $P(x) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}, \{\emptyset\}, \{1, \emptyset\}, \{2,\emptyset\}, \{1,2,\emptyset\} \}$ ? When I write ...
3
votes
2answers
101 views

Confusion about the definition of function

Yesterday I was talking to one of my friends about the definition of function. The formal definition of function is given by Cartesian Products but my friend's question was whether it is possible to ...
2
votes
2answers
38 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
1
vote
1answer
34 views

What is the cardinality of the class of $0$ in $\mathbb{R}$?

What is the cardinality of the class of $0$ in $\mathbb{R}$? In other words: what is the cardinality of the class of all rational Cauchy sequences that converge to $0$?
4
votes
6answers
399 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
0
votes
2answers
33 views

Set theory and logic proof

Problem: Prove that if the sets $A,B,C \in U$, where $U$ is a universal set, then $A \cap B = A \cup B$ if and only if $A = B$ My attempt:We can show that $A \cap B = A \cup B$ if $A = B$ with the ...
3
votes
2answers
57 views

How do I prove that there doesn't exist a set whose power set is countable? [duplicate]

I don't even know where to begin on this one. Let $A$ be a countable set. In other words, $|A| = |\mathbb{N}|$. I'm trying to prove that there doesn't exist an $x$ such that $\mathcal{P}x = A$. ...
1
vote
2answers
52 views

How do I prove that for any set $A$, $|A| < |\mathbb{N}|$ implies that $A$ is finite?

Here's what I've tried so far. Let $A$ be a set and suppose $|A| < |\mathbb{N}|$. By the definition of less than for cardinalities (I'm reading out of Hrbacek's Introduction to Set Theory), this ...
3
votes
2answers
24 views

Given a set $A$, how do I prove that there exists a set of all sets $x$ such that $\bigcup x=A$?

I am working with Zermelo-Fraenkel axioms. Specifically, I am allowed to assume the Axiom of Pair, Axiom Schema of Comprehension, Axiom of Union, and Axiom of Power Set, etc. (not yet allowed to use ...
1
vote
1answer
29 views

Proof on $\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$

Is this proof valid? $\textbf{Claim: }\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$ Proof. Let us suppose that there was an $x\in A$ where $x\neq\varnothing$. Since $x\in \bigcup A ...
0
votes
3answers
52 views

How to come up with bijections?

Is there a good technique for finding bijections in general? Like between the integers and the natural numbers or between [0,1) and (0,1).
4
votes
2answers
43 views

example of uncountable set

I am looking for simple proofs of uncountable sets: I know a set is said to be uncountable if there is no injective function from the set to the natural numbers. I know the set of real numbers is ...
1
vote
1answer
31 views

Definiton of function

Are these two statements true about the definition of a function f from A into B For every element a in A, there exists at least one element b in B such that f(a)=b For every element a in A, there ...
2
votes
5answers
144 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
0
votes
1answer
29 views

Properties of infinity and Pi

Are the decimal points after Pi a countable infinity or uncountable? Can I just map the first decimal point to the first natural number and nth decimal to nth natural number?
1
vote
1answer
29 views

For all set A, B, and C if $(A \cap B) \cup C \subset A \cap (B \cup C)$ then $C \subset A$?

For all set A, B, and C if $(A \cap B) \cup C \subset A \cap (B \cup C)$ then $C \subset A$? Is this a theorem or a false proposition? Help!
1
vote
3answers
44 views

Is $g$ the unique function with this property?

Prove/Disprove: Let $A$ and $B$ be sets and let $f : A \to B$ be a function. If there is a function $g : B \to A$ such that $g\circ f = \operatorname{id}_A$, then $g$ is the unique function with this ...
0
votes
3answers
17 views

Proving a surjective function by given property

Suppose $f:E\rightarrow F$ and for any $A\subset F,A=f(f^{-1}(A))$. Show that f is surjective. What i have tried is $$\text{Let }y\in A $$ $$\{y\}\subset A$$ $$\{y\}= f(f^{-1}{\{y\})}$$ And i stuck ...
11
votes
4answers
926 views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
4
votes
3answers
124 views

Munkres Section 10: How are these order types different?

Let $\mathbb{Z}^+$ denote the set of all positive integers in the usual order, let $n$ be a positve integer, and let the following sets have the dictionary order: $\{1, \ldots, n \} \times ...
1
vote
1answer
41 views

If a function from set $A$ to $B$ is one-to-one, is the function from $P(A)$ to $P(B)$ one-to-one as well?

If $f$ is a function from set $A$ to set $B$, define the function $S_f$ from $2^A$ to $2^B$ by $$S_f(X) = f(X)$$ for each subset $X$ of $A$. If a function $f$ from set $A$ to $B$ is one-to-one, is ...
0
votes
1answer
50 views

Construction of real numbes

How do I prove that the set of real numbers is the set of the power set of the set of natural numbers ? I can understand that the set of reals is uncountable and the set of Natural Numbers is ...
3
votes
1answer
39 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
2
votes
2answers
54 views

How are some infinities larger than other infinities

I heard an expressions, some infinities are larger than others recently, and they stated that it was proved to be so. I haven't been able to find this proof, and ...
0
votes
1answer
32 views

Prove that if $\: \forall_{t \in \mathbb{R}} \: \overline{\overline{A}}_t = c$ then $\overline{\overline{\bigcup_{t \in \mathbb{R}} \: A_t}} = c$

Prove that if $\: \forall_{t \in \mathbb{R}} \: \overline{\overline{A}}_t$ is equal to cardinality $c$, then $\:\overline{\overline{\bigcup_{t \in \mathbb{R}} \: A_t}}$ is also equal to cardinality ...
4
votes
2answers
45 views

Show that $A \subseteq B$ if and only if every subset of A is a subset of B.

Let $A$ and $B$ be sets. Show that $A \subseteq B$ if and only if every subset of $A$ is a subset of $B$. So I know I have to prove this in both directions but this is what I got so far: If if every ...
2
votes
0answers
64 views

Counterexample to an implication

Denote $\bar{A}$ a complement of $A$ in a set $\Omega$ and $A \Delta B = A/B \cup B/A$ the symmetric difference of $A, B$. It is claimed that for a map $\phi := \Omega \rightarrow \lbrace 0, 1 ...
-1
votes
1answer
71 views

Set theory, really struglling, some REAL help please. :)

First I understand power sets. I understand that if we have the power set $X^Y$ such that $X = \{3,2\}$ and $Y = \{1,6\}$ then the power set contains 4 elements $f(3) = 1$, $f(2) = 1$...etc NOW onto ...
3
votes
5answers
88 views

Find a bijection from $\mathbb R$ to $\mathbb R-\mathbb N$

Find a bijection from $\mathbb R \to \mathbb R-\mathbb N$. I want to set my function up such that all natural numbers get mapped to $n+.1$ and reals of the form $n+.1$ to $2n+.1$ is this correct?
0
votes
1answer
36 views

Number of elements of the nth power set of the empty set?

Let n be a natural number find #℘ⁿ(∅) where ℘ⁿ means the n-th power set. I know that it has 2ⁿ where n is the number of elements. Other than this I don't know ...
1
vote
1answer
47 views

Relations on the set of Real Numbers

I need a relation on ℝ that is neither reflexive, nor symmetric, nor transitive. I thought of a ~ b where a=b²+1 (mostly) Not reflexive because: a² ≠ a² + 1 (mostly) Not ...
5
votes
3answers
41 views

Power set of Set differences

Assume that $\mathcal P(A-B)= \mathcal P(A)$. Prove that $A\cap B = \varnothing$. What I did: I tried proving this directly and I got stuck. Let $X$ represent a nonempty set, and let ...
1
vote
1answer
35 views

Is function $f$ also uniformly continuous?

I've been thinking on the following problem lately: Let $(X,d)$ be a metric space and $f_1,f_2,...,f_n: X \rightarrow \mathbb{R}$ and $f(x) = \max\{f_1(x),f_2(x),...,f_n(x) \}$,$x\in X$ If the ...
-7
votes
1answer
41 views

What can we say about the set $\cap U_i$? [on hold]

Let $U_1\supset U_2 \supset......$ be a decresing sequence of open sets in Euclidian 3 space $\mathbb R^3.$ What can we say about the set $\cap U_i$? A. It is infinite. B. It is ...
1
vote
2answers
34 views

An explicative definition of what is meant by $\{A_i\}_{i\in I}$?

What does $\{A_i\}_{i\in I}$ mean exactly? I know it's an index, but what exactly is that?
3
votes
2answers
65 views

logic and set theory proof : $|A \cap B| <|A^C|$

Prove that if $A$ and $B$ are sets then $|A \cap B| <|A^C|$. I'm not sure how I should start this proof. Normally I would turn the proof into set theory notation, but I'm not sure if that works or ...