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
1answer
20 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
6
votes
2answers
246 views

Is the set {a,b} uniquely defined?

First answer to this question would be yes, but consider the following question: How many elements has the set $\{a,\, b\}$? The answer to this question depends on $a$ and $b$: If $a=b$, then ...
0
votes
2answers
35 views

Beginner questions about Sets.

I have a quick question in regard to sets. I am a little confused when I see the notation $A\subseteq B$. How is this different than the sets $A$ and $B$ being identical? I guess some of the confusion ...
0
votes
1answer
27 views

Showing that two intervals are equivalent.

Complete the proof that any two open intervals $(a, b)$ and $(c, d)$ are equivalent by showing that $f(x) = \frac{d-c}{b-a}(x-a) + c$ maps one to one and onto $(c,d)$. I showed one to one by saying ...
2
votes
1answer
49 views

Representation of null set or empty set?

I am having confusion that how to represent null set. Yes it seems like I ask silly question. Well I know null set can be represent either $\{\}$ or $\emptyset$. But can I write null set like ...
0
votes
2answers
27 views

Does $A \subset \cup_{i=1}^{\infty}U_i$ and $B \subset \cup_{n=1}^{\infty}V_n$ imply $A \times B \subset \cup_{i,n}(U_i \times V_n)$?

If $A \subset \cup_{i=1}^{\infty}U_i$ and $B \subset \cup_{n=1}^{\infty}V_n$, how can I show that $A \times B \subset \cup_{i,n}(U_i \times V_n)$? Also, what would it mean for $A \times B \subset ...
4
votes
2answers
79 views

Mathematical concept for formal languages

A formal language is defined as a subset of finite-length strings over an alphabet. It is similar to the mathematical concept "relation", but the lengths of its strings are not fixed. Since the name ...
2
votes
0answers
31 views

Velleman's How to prove it. Partial order proof.

Theorem: Suppose that $R$ is a partial order on $A$, $B_1 ⊆ A$, $B_2 ⊆ A$, $x_1$ is the least upper bound of $B_1$, and $x_2$ is the least upper bound of $B_2$. Prove that if $B_1 ⊆ B_2$ then ...
0
votes
2answers
45 views

Suppose $F$ and $G$ are families of sets.

Suppose $F$ and $G$ are families of sets. Prove that $\bigcup F$ and $\bigcup G$ and are disjoint iff for all $A∈F$ and $B∈G$ , $A$ and $B$ are disjoint. It has been suggested to use contrapositive ...
1
vote
1answer
30 views

Why $[F(X)\leq G(z)] \bigcap [G^{-1}[F(X)] > z]$ is a subset of $F(X)=G(z)$?

If $F(X)<G(z)$ implies $G^{-1}[F(X)]\leq z$, then $[F(X)\leq G(z)] \cap [G^{-1}[F(X)] > z]$, is a subset of $F(X)=G(z)$. I can't understand how does this statement hold, here.
1
vote
2answers
46 views

Cardinality of an infinite set $S$ of real positive numbers such that the addition of the elements of any non empty finite subset is $\leq1$

I have to find the cardinality of an infinite set $S$ of real positive numbers such that the addition of the elements of any non empty finite subset of $S$ is $\leq1$. We are working in ZFC. I have ...
0
votes
1answer
73 views

Can a bijection be constructed between $\mathbb{Q}$ and $\mathbb{R}$

Can a bijection be constructed between $\mathbb{Q}$ and $\mathbb{R}$, such that $f:\mathbb{Q} \to \mathbb{R}$ is a bijective function? I understand that there exists no bijection between $\mathbb{N}$ ...
-5
votes
1answer
62 views

Dividing a set of n elements into k disjoint subsets.

I have been able to do the 1st part. I have not been able to prove the 2nd part. My attempt to the solution :- I took $k$ groups $ a_1, a_2, a_3…, a_k $ Let $a_1$ group has $b_1$ similarly so ...
3
votes
4answers
291 views

Relations are just sets of ordered pairs?

If the definition of a relation is that it is a set of ordered pairs, how come two relations are not equal if they contain the same elements but aren't on the same sets? For example, Let $R_1$ be a ...
1
vote
3answers
68 views

Proving the open interval $(0,1)$ is uncountable [duplicate]

I am currently able to prove this statement using the Cantor diagonalisation argument, my question is whether there is another way (more simple or more complex) to prove this statement, without ...
4
votes
2answers
54 views

Is there a mistake in this question: $\forall a\in A: |\{x\in A:x\le a \}|=|\{ y\in B :y\le a \}|$?

Two ordered sets $(A,\le_A), (B,\le_B)$ and there's an isomorphic function $f:A\to B$ Prove $\forall a\in A: |\{x\in A:x\le a \}|=|\{ y\in B :y\le a \}|$ I think there's a mistake in this ...
0
votes
2answers
44 views

Does an injective function imply two sets have same cardinality?

In the book "A first course in abstract algebra" by John B. Fraleigh, he states in the introduction chapter (which deals with sets and relations) that for two sets $X$ and $Y$, they have the same ...
1
vote
2answers
140 views

Do transcendental numbers outnumber real numbers?

I am not a mathematics student, but just out of curiosity I was checking out a website which explains the basics of 'Chaos Theory' to the layman. In this site was the sentence : transcendental ...
0
votes
3answers
72 views

Is this statement true, false, or not a mathematical statement?

$ \forall x \in X: \left \{x \right \} \in 2^X $ I'm just really unsure about this one, so please help me out. Thanks!
0
votes
1answer
27 views

Proving that definitions of closures are equal

I have been working through Herbert Endertons Elements of set theory and I have stumbled upon an exercise which I can not solve.Here is how it goes: Let $A \subseteq B$ and let $f:B\to B$. Now let ...
1
vote
1answer
19 views

Injective/Surjection/Bijection

How would you handle the h(x) case to see if it is surjective or injective? Also, how would you prove/disprove that it is a bijection. I know you have to show if it is injective and surjective, but ...
1
vote
1answer
25 views

How to prove a bijection?

I know what a bijection is and how to prove it when given a function, but how to do it when you are only given sets.
0
votes
1answer
87 views

Is {$x|x=x\times x$} a set?

Is {$x|x=x\times x$} a set? We are working in ZFC. I think it is not a set, but I do not know how to prove it.
1
vote
4answers
89 views

What axiom allow the construction of a set using the following notation $\{ x : P(x)\}$, where $P(x)$ is a statement about $x$?

What axiom allow the construction of a set using the following notation $\{ x : P(x)\}$, where $P(x)$ is a statement about $x$ ? If I'm thinking in terms of a process, then the construction $\{ ...
2
votes
1answer
49 views

Ordinal $10^\omega$

$10^\omega$ = $10 \cdot 10 \cdot 10 \cdot ...= \lim_{\alpha \lt \omega} (10^\alpha) = \omega$. Are my thoughts correct? Is this sufficient explanation, given the ordinal arithemtic proved from ZFC?
2
votes
1answer
408 views

Biggest countable ordinal number

I need to find biggest countable ordinal number. But I am sure there is no one, if I understand proofs and definitions correctly. So here are my idea: Suppose there is biggest countable ordinal number ...
0
votes
1answer
17 views

Prove if $a\in A$ is a maximum then $f(a)\in B$ is maximum and if $(A,\le_A)$ is totally ordered then $(B,\le_B)$ is totally ordered

Two ordered sets $(A,\le_A), (B,\le_B)$ and there's an isomorphic function $f:A\to B$ Prove if $a\in A$ is a maximum then $f(a)\in B$ is maximum. if $(A,\le_A)$ is totally ordered then ...
0
votes
1answer
23 views

Order of cardinal number

I am puzzled. Wikipedia says: "|X| ≤ |Y| means that there exists an injective function from X to Y." Let's see sets A and B: A = {1,2,3} and B = {1,2}. f: A → B: 1 ↦ 1, 2 ↦ 2. f is injective, but |B| ...
0
votes
1answer
37 views

Help on understanding how to express sets and their relations graphically

Let $A=\{0,1\}, B=\{a,b,c\}, R=id_A, S=\{(a,b),(a,c) \}\cup id_B$ Express graphically the following: $(A,R)+(B,S)\\ (B,S)+(A,R)\\ (A,R)\times(B,S)\\ (B,S)\times(A,R)$ I'm not sure how ...
0
votes
0answers
51 views

Would like to confirm answer (regarding sets)

As you might know from my precious questions, I am pretty weak with quantifiers. Below is my solution to the stated problem, if incorrect, could someone explain why? My attempted solution: ...
0
votes
2answers
49 views

Proving a Function

Consider the function $f\colon[0,+\infty)\to X$ where $f(x) = 3\sqrt{x+5}-1$. (a) Determine a set $X$ for which $f$ is onto, and then prove that $f$ is onto using your $X$. Really stuck and ...
0
votes
1answer
50 views

Question regarding proving statements of sets

I've been having some trouble with this question while preparing for college algebra. Can anybody give an explanation of the proofs for the following question step by step so that I can comprehend? ...
0
votes
2answers
30 views

Reflexive/Symmetric/Antisymmetric/Transitive

I am having issues identifying if the following are reflexive/symmetric/antisymmetric/transitive. Could anybody help me out? I have the book definitions but I'm confused on really the application of ...
0
votes
2answers
50 views

Equivalence relations and equivalence classes

I dont know how to start this proof? Also, our professor did not explain equivalence classes fully so I am not understanding them very well.
2
votes
1answer
54 views

How to Prove it 4.1 ex.10

Prove that for any sets A, B, C, and D, if A × B and C × D are disjoint, then either A and C are disjoint or B and D are disjoint. Proof(someones). Suppose (A X B) and (C X D) are disjoint. Let (x,y) ...
0
votes
3answers
23 views

Existence of a one-to-one function (injection) from one finite set to another

Consider two finite sets, $A$ and $B$. Is it fine to say that “an injection $f \colon A \rightarrow B$ exists if and only if $|A| \leq |B|$”? If it is, could you please suggest as to how I might ...
3
votes
3answers
73 views

Notation for choosing the k smallest elements from a set of integer

Is there any specific notation for picking $k$ elements from a set which are the smallest? Ex: {$1,3,5,7,9,11$} with $k = 3 \Rightarrow$ We want $1,3,5$
0
votes
1answer
26 views

How should this definition of a family with corresponding index set be interpreted?

Does the following definition of a family imply that there exist a surjection from $I$ onto the family ? Or should it be interpreted as a injective partial function from $I$ to the family ? ...
1
vote
2answers
58 views

Any infinite set partitioned into a set of countably infinite sets?

Prove that if $s$ is infinite, then it can be partitioned into a set of countably infinite sets $\mathcal{A}$. That is: $\bigcup \mathcal{A}=s$ $\forall a\in \mathcal{A}, a$ is countably ...
0
votes
1answer
56 views

Number of all finite sequences from a set? [duplicate]

Given a set $\Sigma$ of letters, apply the Kleene star operation to it, and we get $\Sigma^*$, the set of all finite-length sequences from $\Sigma$, called strings (allowing a letter appearing more ...
1
vote
5answers
95 views

A null set is a subset of other sets

I was wondering, how can a null set be a subset of other sets? Could anyone explain the idea in non technical terms, I'm just a beginner. :) Thank you!
1
vote
0answers
53 views

What's with this proof that if $E_n$ is countable, then $\bigcup E_n$ is also countable?

I'm a student starting Rudin's Principles right now. I'm confused by the proof that if $E_n$ is countable, then $\bigcup E_n$ is also countable. Here it is, in image format since I don't know how to ...
2
votes
1answer
31 views

Semialgebra logical error

I was following a proof on Rosenthal's, A first look at rigorous probability theory book, but I believe that one step flawed. Let me set up: $\mathcal{J}$ is a semialgebra of subsets of $\Omega$. ...
5
votes
1answer
52 views

Halmos on Definability and Luzin on Division by 0

For a successful introduction of a new symbol (e.g. '$\emptyset$') into a mathematical discourse it is necessary and sufficient that the symbol refer to something (e.g. Existence + Specification in ...
0
votes
1answer
15 views

Continuity of restriction map

Consider a map $f:X\rightarrow Y$ and suppose $X=\bigcup_i U_i$ is a union of open subsets. Prove that if all the restrictions $f_i=f|_{U_i}:U_i\rightarrow Y$ are continuous, then $f$ is continuous. ...
0
votes
5answers
52 views

Prove or disprove $X \backslash A \cup B = (X\backslash A) \cap (X \backslash B)$

We have to prove or disprove the statement $X \backslash A \cup B = (X\backslash A) \cap (X \backslash B)$ I can draw the picture and what I'm getting is that this statement is true, but I don't ...
3
votes
1answer
79 views

How functions definided by cases, can be written in formal ZFC set theory?

Function definition by cases. It is usual define for example the absolute value of Real number as $$ \left|x\right| = \begin{cases} x & if & x> 0 \\ -x & if &x < 0 \\ 0 & ...
1
vote
2answers
21 views

Intersection of infinite sets

Let $B_k=\{k, k+1, k+2,...\}$ Then why is it that $\bigcap_{k=1}^{\infty}B_k=\emptyset$ ? Is it not the case that $\infty$ is in every set?
3
votes
0answers
60 views

Countably infinite set and uncountable collection of subsets

How can I Prove or disprove that every uncountable collection of subsets of a countably infinite set must have two members whose intersection has at least 2010 elements?
1
vote
1answer
49 views

Simple fact about class of sets.

I have a simple question which is very trivial for the other people, I guess. However, I never fully understand the argument completely. Take any $X\neq\emptyset$ and let $\mathbf{S}$ be an arbitrary ...